Generate All Possible IP Addresses From Given Numeric String in Java
1. 개요
이 튜토리얼에서는 주어진 숫자 문자열에서 모든 가능한 IP 주소를 생성하는 다양한 방법을 탐구합니다. 이 문제는 흔한 면접 질문입니다. 먼저 문제 설명을 깊이 있게 살펴보고, 이를 해결하기 위한 여러 기술, 즉 브루트 포스, 백트래킹 및 동적 프로그래밍을 다룰 것입니다.
2. 문제 설명 이해하기
우리는 숫자만 포함된 문자열 S를 제공받습니다. 목표는 S에 점을 삽입하여 형성할 수 있는 모든 가능한 유효한 IP 주소를 찾고 반환하는 것입니다. 우리는 어떤 숫자도 제거하거나 순서를 변경할 수 없으며, 결과는 어떤 순서로도 반환될 수 있습니다.
예를 들어 주어진 문자열 “101024”의 경우, 우리는 다음과 같은 출력을 얻게 됩니다:
["1.0.10.24","1.0.102.4","10.1.0.24","10.10.2.4","101.0.2.4"]위 출력은 주어진 문자열로 형성할 수 있는 모든 유효한 IP 주소를 나열합니다. 유효한 IPv4 주소는 점으로 구분된 4개의 옥텟으로 구성됩니다. 각 옥텟은 0에서 255 사이의 숫자여야 합니다. 즉, 유효한 IPv4 주소는 다음과 같습니다:
0.0.0.0
192.168.0.8
234.223.43.42
255.255.255.03. 반복적 접근법
이 접근법에서는 세 개의 중첩 루프를 사용하여 문자열을 4개의 부분으로 나누기 위한 가능한 위치를 반복합니다. 외부 루프는 첫 번째 부분을 반복하고, 중간 루프는 두 번째 부분을, 내부 루프는 세 번째 부분을 반복합니다. 나머지 부분은 문자열의 네 번째 세그먼트로 간주합니다.
세그먼트 조합을 생성한 후, 각각의 세그먼트를 검증하여 IP 주소의 유효한 부분인지 확인하기 위해 isValid() 메소드를 사용할 것입니다. isValid() 메소드는 주어진 문자열이 IP 주소의 유효한 부분인지 확인하는 역할을 합니다. 이 메소드는 정수 값이 0과 255 사이인지 확인하고 선행 0이 없도록 합니다:
public List<String> restoreIPAddresses(String s) {
List<String> result = new ArrayList<>();
if (s.length() < 4 || s.length() > 12) {
return result;
}
for (int i = 1; i < 4; i++) {
for (int j = i + 1; j < Math.min(i + 4, s.length()); j++) {
for (int k = j + 1; k < Math.min(j + 4, s.length()); k++) {
String part1 = s.substring(0, i);
String part2 = s.substring(i, j);
String part3 = s.substring(j, k);
String part4 = s.substring(k);
if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
result.add(part1 + "." + part2 + "." + part3 + "." + part4);
}
}
}
}
return result;
}
private boolean isValid(String part) {
if (part.length() > 1 && part.startsWith("0")) { return false; }
int num = Integer.parseInt(part);
return num >= 0 && num <= 255;
}restoreIPAddresses() 메소드는 모든 가능한 유효한 IP 주소를 생성하여 반환합니다. 또한 문자열 길이가 4에서 12자 사이에 없는 경우를 확인하고, 그 경우에는 유효한 IP 주소를 형성할 수 없으므로 빈 목록을 반환합니다.
우리는 중첩 루프를 사용하여 세 점의 모든 가능한 위치를 반복합니다. 이는 시간 복잡도를 O(n2)로 증가시킵니다. 외부 루프는 고정된 수의 반복을 가지므로 O(n3)가 아닙니다. 또한 각 반복 동안 임시 하위 문자열을 생성하고 있어 전체 공간 복잡도가 O(n)로 증가합니다.
4. 백트래킹 접근법
백트래킹 기법을 사용하여, 문자열을 4부분으로 나누어 모든 가능한 IP 주소를 생성합니다. 각 단계에서 우리는 같은 isValid() 메소드를 사용하여 문자열이 비어 있지 않고 선행 0이 없는지 검증합니다. 유효한 문자열인 경우 다음 파트로 넘어갑니다. 모든 4부분이 생기고 모든 문자를 사용했다면, 이들을 결과 목록에 추가합니다:
public List<String> restoreIPAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(result, s, new ArrayList<>(), 0);
return result;
}
private void backtrack(List<String> result, String s, List<String> current, int index) {
if (current.size() == 4) {
if (index == s.length()) {
result.add(String.join(".", current));
}
return;
}
for (int len = 1; len <= 3; len++) {
if (index + len > s.length()) { break;
}
String part = s.substring(index, index + len);
if (isValid(part)) {
current.add(part);
backtrack(result, s, current, index + len);
current.remove(current.size() - 1);
}
}
}백트래킹 함수는 문자열을 3자리 이하의 각 정수 세그먼트로 나눕니다. 이는 문자열을 나누는 34 가능한 방법을 생성합니다. 각 세그먼트가 유효한지 평가하는 데는 O(1)의 시간이 소요되며, 이는 길이와 범위를 확인하는 것으로 이루어집니다. 가능한 구성의 수가 34로 고정되기 때문에, 시간 복잡도는 O(1)로 단순화됩니다.
재귀 깊이는 IP 주소에 정확히 4개의 세그먼트가 있기 때문에 제한됩니다. 따라서 공간 복잡도도 상수로 단순화되어 O(1)이 됩니다.
5. 동적 프로그래밍 접근법
동적 프로그래밍은 재귀 공식을 사용하여 솔루션을 찾는 인기 있는 알고리즘 패러다임입니다. 이 접근법은 문제를 더 작은 하위 문제로 나누기 때문에 분할 정복 전략과 유사합니다. 이전에 계산된 값의 결과를 저장하는 배열을 사용합니다.
이제 유효한 IP 접두사를 저장하기 위해 dp 배열을 사용할 것입니다. 먼저 dp[i][j]가 i번째 문자까지의 모든 가능한 IP 주소 세그먼트를 저장하는 2D 리스트 dp를 초기화합니다. 그 후 가능한 세그먼트 길이(1에서 3까지)를 확인하고, 각 세그먼트를 isValid() 메소드를 사용해 검증합니다. 세그먼트가 유효한 경우, 이전 상태의 접두사에 추가합니다. 유효한 IP 주소의 최종 결과를 dp[n][4]에 저장하고 반환합니다:
public List<String> restoreIPAddresses(String s) {
int n = s.length();
if (n < 4 || n > 12) { return new ArrayList<>();
}
List<String>[][] dp = new ArrayList[n + 1][5];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 4; j++) {
dp[i][j] = new ArrayList<>();
}
}
dp[0][0].add("");
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= 4; k++) {
for (int j = 1; j <= 3 && i - j >= 0; j++) {
String segment = s.substring(i - j, i);
if (isValid(segment)) {
for (String prefix : dp[i - j][k - 1]) {
dp[i][k].add(prefix.isEmpty() ? segment : prefix + "." + segment);
}
}
}
}
}
return dp[n][4];
}dp 배열의 초기화는 O(n*4)의 시간이 소요되며, O(n)으로 단순화됩니다. dp 테이블을 채우는 중첩 루프는 O(n*4*3)의 시간을 소요하며, 이것은 O(n)으로 단순화됩니다. 공간 복잡도는 또한 O(n*4)로, 이것은 O(n)으로 단순화됩니다.
6. 결론
이 기사에서는 주어진 숫자 문자열에서 모든 가능한 IP 주소 조합을 생성하는 방법에 대해 논의하고, 이를 해결하기 위한 다양한 접근법을 이해했습니다. 반복적 접근법은 간단하지만 시간 복잡도가 높습니다 (O(n2)). 더 나은 성능을 위해, 우리는 동적 프로그래밍 접근법을 사용할 수 있으며, 이 방법은 O(n)이라는 더 나은 시간 복잡도를 제공합니다.
백트래킹 프로그래밍 접근법은 논의한 다른 접근법들 중에서 가장 효율적인 것으로 나타났습니다. 런타임이 모든 접근법 중에서 가장 좋았기 때문입니다 (O(1)).
항상 그렇듯이 이 기사에서 사용된 코드는 GitHub에서 확인할 수 있습니다.
