문제 소개
숫자로만 구성된 문자열이 하나 주어져 있다고 가정해 보겠습니다. 이 문자열을 재구성하여 만들 수 있는 모든 유효한 IP 주소 조합을 찾아야 합니다. 여기서 유효한 IP 주소란 정확히 네 개의 정수(각 정수는 0부터 255 사이의 값)가 마침표(.)로 구분되어 있는 형태를 의미합니다.
예를 들어 입력이 ip = "25525511136"라면, 출력은 다음과 같습니다.
["255.255.11.136", "255.255.111.36"]
해결 접근 방법
이 문제는 백트래킹(backtracking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 전체 흐름을 단계별로 살펴보겠습니다.
1단계: convertToNum() 함수 정의
- 매개변수로 문자열 s, 시작 인덱스 start, 끝 인덱스 end를 받습니다.
- num := 0으로 초기화합니다.
- i를 start부터 end까지 1씩 증가시키며 반복합니다.
- num := (num * 10) + (s[i] - '0')
- 반복 중 num이 255를 초과하면 10000을 반환하여 유효하지 않음을 표시합니다.
- 반복이 정상적으로 끝나면 num을 반환합니다.
2단계: addDots() 함수 정의
- positions 배열을 매개변수로 받습니다.
- 빈 문자열 res를 준비합니다.
- positions의 각 요소를 문자열로 변환해 res에 이어 붙이고, 마지막 요소가 아닌 경우에는 "."을 추가합니다.
- 완성된 IP 주소 문자열 res를 반환합니다.
3단계: solve() 함수 정의 (백트래킹 핵심 로직)
- 매개변수: 문자열 s, 결과 배열 result, positions 배열, dotCount(기본값 3), startIndex(기본값 0)
- dotCount가 0이 되고 남은 문자가 존재한다면:
- 남은 부분을 convertToNum()으로 변환합니다.
- 값이 0 이상 255 이하이면 positions에 추가한 뒤 addDots()로 완전한 IP 문자열을 생성합니다.
- 생성된 문자열의 길이에서 마침표 3개를 제외한 길이가 원래 문자열의 길이와 일치하면 result에 삽입합니다.
- 그 외의 경우, startIndex부터 문자열 끝까지 반복하면서:
- convertToNum(s, startIndex, i)로 부분 문자열을 숫자로 변환합니다.
- 값이 유효하면 positions에 추가하고, dotCount를 1 감소시켜 재귀 호출합니다.
- 재귀 호출이 끝나면 positions의 마지막 요소를 제거하여 다음 경우의 수를 탐색합니다(백트래킹).
4단계: genIp() 함수 정의
- 결과 배열 result와 position 배열을 선언합니다.
- solve(s, result, position)을 호출합니다.
- result를 반환합니다.
마지막으로 main 함수에서 genIp(A)를 호출하여 결과를 얻습니다.
C++ 구현 예제
아래 구현 예제를 통해 좀 더 명확하게 이해해 보겠습니다.
#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> get_ip(string A) {
return genIp(A);
}};
main(){
Solution ob;
string ip = "25525511136";
print_vector(ob.get_ip(ip));
}입력
25525511136
출력
[255.255.11.136, 255.255.111.36]
출력 끝에 붙는 쉼표는 예제의 print_vector() 함수가 마지막 요소 뒤에도 쉼표를 출력하기 때문이며, 실제로 유효한 IP 주소는 255.255.11.136과 255.255.111.36 두 가지입니다.