LeetCode: 93번 (Restore IP Addresses) [JAVA]

문제 링크

https://leetcode.com/problems/restore-ip-addresses/

Restore IP Addresses - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 s의 길이가 12를 초과한다면, 빈 리스트 반환
2. IP 주소 문자열 생성을 위한 재귀함수 생성 (인자로는 문자열 s와 s의 위치를 나타내는 index, StringBuilder, 점의 개수를 나타내는 dotCount)
   1) 기저조건의 경우 dotCount가 4에 도달했을 때, index가 s의 길이를 넘었다면 여태까지의 StringBuilder 속 문자열의 부분 문자열을 가져와 리스트에 추가하고, 넘지 못했다면 탐색 종료
   2) 주어진 index + 1부터 문자열의 끝 혹은 index + 3 이전 까지, index 부터 해당 길이까지의 부분 문자열을 가져온 다음에 해당 부분 문자열이 IP 주소 속 구간을 만족한다면 해당 부분문자열 + ".'을 추가한 다음 재귀 함수를 다시 호출
   3) 이후 추가했던 부분문자열 + "." 부분을 다시 제거
3. 탐색 이후 결과 리스트 반환

 주어진 문자열을 적당히 나누어, 만족하는 IP 주소 형태를 모두 문자열로 만들어 리스트로 반환하면 되는 문제이다. 이런 모두 만족하는 결과물을 만들기 위해서는 대개 백트래킹 기반 재귀 탐색을 사용하기 때문에, 이를 활용하여 문제를 풀 수 있다.
 우선 IP 주소의 최대 길이는 숫자 3개의 형태로 4개 구간이 생성되기 때문에, 주어진 s의 최대 길이가 12를 넘는다면 바로 빈 리스트를 반환한다. 이후에는 재귀 함수를 호출하면 되는데, 이 때 호출할 재귀함수의 경우는 다음과 같다.
 인자로는 먼저 문자열 s, s의 특정 위치를 나타낼 index, 문자열을 담을 StringBuilder, 그리고 IP 주소 형태를 구성하는데 사용한 "."의 개수를 나타낼 dotCount이다. 해당 재귀함수의 기저조건은 dotCount가 4에 도달한 경우로, 만약 이 때 index가 s의 길이 이상이라면 s를 모두 사용해 IP 주소 형태의 문자열을 구성한 것이기 때문에 결과 리스트에 추가한다. 그 다음 탐색의 경우 반복문을 통해 i = index 부터 s의 끝 혹은 index + 3 중 더 작은 값까지 탐색을 진행한다. 이 때 s에서 index ~ i+1까지의 부분 문자열을 추출한 다음, 해당 부분 문자열이 IP 주소 속 숫자 형태를 만족하는지 체크한다. 만약 해당 문자열이 두 자릿수 이상이면서 0으로 시작하면 안되고, 숫자 자체는 0~255 사이의 값을 만족해야 한다. 이후 만약 해당 조건을 만족했다면, 해당 부분 문자열 + "."을 인자로 받은 StringBuilder에 추가하고, 다음 재귀 함수를 호출한다. 이후엔 백트래킹을 위해 앞서 붙였던 문자열을 다시 제거해주면된다.
 탐색이 완료된 이후엔 결과 문자열이 추가된 리스트를 반환하면 된다.

 

class Solution {
    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) {//3*4 개의 IP 구성을 넘는 경우
            return result;
        }
        search(0, new StringBuilder(), 0, s);
        return result;
    }

    void search(int index, StringBuilder sb, int dotCount, String s) {
        if (dotCount == 4) {//4개의 구간을 모두 구성했다면
            if (index >= s.length()) {//모든 숫자 문자열을 다 사용했다면
                result.add(sb.substring(0, sb.length() - 1));
            }
            return;
        }

        for (int i = index; i < Math.min(s.length(), index + 3); i++) {//최대 3개 건너만큼
            String substr = s.substring(index, i + 1);
            int toNum = Integer.parseInt(substr);

            if ((!(substr.length() > 1 && substr.startsWith("0")))
                    && (0 <= toNum && toNum <= 255)) {//부분 문자열이 IP 구간 하나의 조건을 만족한다면 다음 재귀 탐색 진행
                sb.append(substr).append('.');
                search(i + 1, sb, dotCount + 1, s);
                sb.delete(sb.length() - substr.length() - 1, sb.length());
            }
        }
    }
}

결과