문제 소개
숫자로만 이루어진 문자열이 하나 주어졌다고 가정해 봅시다. 우리는 이 문자열을 복원하여 가능한 모든 유효한 IP 주소 조합을 반환해야 합니다. 유효한 IP 주소는 정확히 네 개의 정수(각 정수는 0부터 255 사이의 값)가 마침표(.) 하나로 구분된 형태로 구성됩니다.
예를 들어 입력이 "25525511135"라면, 출력은 다음과 같습니다.
["255.255.11.135", "255.255.111.35"]
해결 접근 방법
이 문제는 재귀 호출과 백트래킹(backtracking)을 활용하여 해결할 수 있습니다. 전체 알고리즘은 다음 단계로 진행됩니다.
- convertToNum() 함수를 정의합니다. 이 함수는 문자열 s, 시작 인덱스 start, 끝 인덱스 end를 매개변수로 받습니다.
- num := 0으로 초기화합니다.
- i := start부터 i <= end까지 반복하면서 다음을 수행합니다.
- num := (num * 10) + (s[i] - '0'의 아스키 값)
- 만약 num > 255라면 10000을 반환합니다.
- num을 반환합니다.
- addDots() 함수를 정의합니다. 이 함수는 positions 배열을 받습니다.
- res := 빈 문자열로 초기화하고, x := 0, posIndex := 0으로 설정합니다.
- positions의 크기만큼 반복하면서 다음을 수행합니다.
- num := positions[i]
- 문자열 str1을 생성합니다.
- temp := num을 문자열로 변환한 값
- res := res + temp
- 만약 i < positions 크기 - 1이라면 res 뒤에 "."을 추가합니다.
- res를 반환합니다.
- solve() 함수를 정의합니다. 이 함수는 문자열 s, 문자열 배열 result, positions 배열, 그리고 각각 기본값이 3과 0으로 초기화되는 dotCount와 startIndex를 받습니다.
- dotCount가 0이고 ((s 크기 - 1) - startIndex + 1) >= 1인 경우 다음을 수행합니다.
- temp := convertToNum(s, startIndex, s 크기 - 1)
- temp가 0 이상 255 이하라면:
- positions 끝에 temp를 삽입합니다.
- res := addDots(positions)
- res의 크기 - 3이 s의 크기와 같다면 result에 res를 삽입합니다.
- 반환합니다.
- i := startIndex부터 s의 크기 미만까지 반복하면서 다음을 수행합니다.
- temp := convertToNum(s, startIndex, i)
- temp가 0 이상 255 이하라면:
- positions 끝에 temp를 삽입합니다.
- solve(s, result, positions, dotCount - 1, i + 1)을 재귀 호출합니다.
- positions에서 마지막 요소를 제거합니다(백트래킹).
- genIp() 함수를 정의합니다. 이 함수는 문자열 s를 받습니다.
- result 배열과 position 배열을 정의합니다.
- solve(s, result, position)을 호출합니다.
- result를 반환합니다.
- main 메서드에서 genIp(A)를 호출합니다.
구현 예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
lli convertToNum(string s,int start, int end){
lli num = 0;
for (int i = start; i <= end; i++) {
num = (num * 10) + (s[i] - '0');
if (num > 255)
return 10000;
}
return num;
}
string addDots(vector <int> positions){
string res = "";
int x = 0;
int posIndex = 0;
for (int i = 0; i < positions.size(); i++) {
int num = positions[i];
ostringstream str1;
str1 << num;
string temp = str1.str();
res += temp;
if (i < positions.size() - 1)
res += ".";
}
return res;
}
void solve(string s, vector <string> &result,vector <int> positions, int dotCount = 3, int startIndex = 0){
if (!dotCount && ((s.size() - 1) - startIndex + 1) >= 1) {
int temp = convertToNum(s, startIndex, s.size() - 1);
if (temp >= 0 && temp <= 255) {
positions.push_back(temp);
string res = addDots(positions);
if (res.size() - 3 == s.size()) {
result.push_back(res);
}
}
return;
}
for (int i = startIndex; i < s.size(); i++) {
int temp = convertToNum(s, startIndex, i);
if (temp >= 0 && temp <= 255) {
positions.push_back(temp);
solve(s, result, positions, dotCount - 1, i + 1);
positions.pop_back();
}
}
}
vector<string> genIp(string s){
vector<string> result;
vector<int> position;
solve(s, result, position);
return result;
}
vector<string> restoreIpAddresses(string A) {
return genIp(A);
}};
main(){
Solution ob;
print_vector(ob.restoreIpAddresses("25525511135"));
}입력
"25525511135"
출력
[255.255.11.135, 255.255.111.35]
알고리즘 핵심 정리
이 알고리즘의 동작 원리를 정리하면 다음과 같습니다.
- 백트래킹: 각 단계에서 1~3자리씩 잘라낸 숫자가 유효한 범위(0~255)에 속할 때만 다음 단계로 진행하고, 유효하지 않으면 이전 상태로 되돌아갑니다.
- 조기 종료: convertToNum()은 부분 문자열을 숫자로 변환하는 도중 255를 초과하면 즉시 실패 신호(10000)를 반환하여 불필요한 탐색을 줄입니다.
- 결과 검증: 네 번째 조각까지 처리한 후, 마침표 3개를 제외한 결과 문자열의 길이(res.size() - 3)가 원래 문자열 길이와 일치하는지 확인함으로써 선행 0 등으로 인한 잘못된 조합을 걸러냅니다.