일단 이 문제는 1시간 반만에 풀었다. 걍 틀렸다고 생각한다
특정 조건에 따라 string을 디코딩 하는 문제다.
2[abc]ggg -> abcabcggg
2[a3[bbb]] -> abbbabbbabbb
2[a]3[b] -> aabbb
위와 같이 숫자[X] 와 같이 구성된 문자열은 숫자만큼 X문자열을 반복하는 거다. 숫자는 정수다.
int recursive(string s, int printIdx, string& result) {
int lastIdx = 0;
int k = printIdx;
int t = printIdx;
string temp = "";
int iterSize;
//
// while (s[i] >= ' 0 ' && s[i] <= ' 9 ' ) {
// Cnt = cnt * 10 + s[i++] - ' 0 ' ;
// }
// iteration 숫자 찾기
// 숫자가 아니면 스트링 끝까지 || 숫자를 만나거나 ||
if(s[printIdx] < '0' || s[printIdx] > '9') {
int idx = printIdx;
while(true) {
if(idx >= s.length() || s[idx] > '9' || s[idx] < '0') {
return idx;
}
result += s[idx];
}
}
// 숫자면 ]일 때까지 찾고
while(true) {
if(s[t] == '[') {
break;
}
temp += s[t];
t += 1;
}
cout<<"temp"<<temp<<endl;
iterSize = stoi(temp);
for(int i = 0; i< iterSize; i++) {
k = printIdx + t - 1;
while(true) {
if(s[k] >= '0' && s[k] <= '9') {
} else if(s[k] == '[') {
lastIdx = recursive(s, k + 1, result);
k = lastIdx;
} else if(s[k] == ']' || k>= s.length()) {
break;
} else {
result += s[k];
// cout<<s[k];
}
k += 1;
}
}
if(k < lastIdx) {
return lastIdx;
}
return k;
}
이거 하다가 점점 코드가 산으로 가는거 같아서.. 포기하고 답을 봤다.
일단 재귀에 넘기려고 한 정보는 1. string s : 전체 스트링 2. int printIdx : 출력이 시작되는 index 3. string result: 결과 string
재귀함수의 task는 result에 string 계속 누적시키기. 반환값은 마지막으로 가리킨 index를 반환.
2번째 시도
string decodeString(string s) {
int index = 0;
string result = "";
// return decode(s, index);
decode(index, )
return result;
}
void decode(int &index, int iterSize, string s, string result) {
for(int k = 0; k<iterSize; k+=1) {
int i = index;
while(index<s.size() || s[i] != ']') {
// 문자면
if (s[i] < '0' || s[i] > '9') {
result += s[i];
} else {
int nextIter = 0;
while(s[i] >= '0' && s[i] <= '9') {
nextIter = nextIter * 10 + s[i] - '0';
}
i++;
decode(i, nextIter, s, result);
}
}
}
}
iterSize를 전달해주려다보니..
숫자여도 정수이기 때문에 2자리 수 이상일 수 있음
결국엔 iterSize를 재귀함수에서 호출하지 않는 편이 나았다.
재귀함수의 단위가 스트링만 result에 저장.
재귀를 몇번 호출할지에 대해서는 인자로 받지 않고 재귀함수 내에서 처리.
2번째 시도수정_
void decode(int &index, string s, string& result) {
int i = index;
// or가 아닌 and인 이유는 종료 조건이 두가지 조건을 모두 충족해야함. ]는 스트링을 모두 탐색하기 전에 만날 수 있기 때문.
while(index<s.size() && s[i] != ']') {
// 문자면
if (s[i] < '0' || s[i] > '9') {
result += s[i];
} else {
int nextIter = 0;
while(s[i] >= '0' && s[i] <= '9') {
nextIter = nextIter * 10 + s[i] - '0';
i+=1;
}
i++;
for(int j = 0; j<nextIter; j++) {
decode(i, s, result);
}
}
i+=1;
}
}
decode 재귀함수 호출시, index값을 초기화 해줘야함
decode 순환함수에서 동일한 작업을 nextIter만큼함.
걍 string을 리턴받아서 result에 반복문돌려서 붙여주는게 효율적이고 로직(index 초기화) 추가안해도됨.
3번째 시도수정__
string decode(int &i, string s) {
string result = "";
// int i = index;
// or가 아닌 and인 이유는 종료 조건이 두가지 조건을 모두 충족해야함. ]는 스트링을 모두 탐색하기 전에 만날 수 있기 때문.
int n = (int) s.length();
while(i < n && s[i] != ']') {
cout<<n<<endl;
// 문자면
if (s[i] < '0' || s[i] > '9') {
result += s[i];
i+=1;
} else {
int nextIter = 0;
while(s[i] >= '0' && s[i] <= '9') {
nextIter = nextIter * 10 + s[i] - '0';
i+=1;
}
i++;
string temp = decode(i, s);
i+=1;
for(int j = 0; j<nextIter; j++) {
result += temp;
}
}
}
return result;
}
string decodeString(string s) {
int index = 0;
return decode(index, s);
}
찾은 정답
string decodeString(string s) {
int index = 0;
return decode(s, index);
}
string decode(string s, int index) {
string result "";
int i = index;
while(i < result.size() && s[i] != ']') {
if (s[i] < '0' || s[i] > '9') {
result += s[i++];
} else {
int cnt = 0;
while (s[i] >= '0' && s[i] <= '9') {
cnt = cnt * 10 + s[i++] - '0';
}
i++;
string temp = decode(s, i);
i++;
while (cnt-- > 0) {
result += temp;
}
}
}
return result;
}
정답을 수도코드로 작성해보면
재귀함수는
return result: 출력되야할 스트링.
task : s[i]가 ]거나 i가 입력받은 문자열 길이보다 커지면
숫자면
숫자 완성되면
반환받은 문자열을 숫자만큼 반복문 돌려서 result에 추가
summary
재귀함수 호출 횟수를 재귀함수의 인자로 넣어줬는데(재귀함수의 task는 출력만해라 라고 정해서),
이렇게 하게 될 경우 재귀 함수 첫 호출 때, 몇번 호출해야하는지 정해줘야한다.(재귀 호출 전, 재귀 함수 내부 이렇게 두곳에서 코드가 중복된다.)
"100" 을 100으로 표현하기 위해 아래와 같은 코드를 순간적으로 생각했는데
while(s[i] >= '0' && s[i] <= '9') {
nextIter = nextIter * 10 + s[i] - '0';
i+=1;
}
