문제 개요
인코딩된 문자열이 주어졌을 때, 이를 디코딩하여 원래 문자열을 반환하는 문제입니다. 인코딩 규칙은 k[encoded_string] 형태로, 대괄호 안의 문자열(encoded_string)이 정확히 k번 반복된다는 의미입니다.
단, 원본 데이터에는 숫자가 포함되어 있지 않으며, 숫자는 오직 반복 횟수 k를 나타내는 용도로만 사용됩니다.
예를 들어 입력이 "1[ba]2[na]"라면, 출력은 "banana"가 됩니다.
해결 접근 방법
이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- 빈 스택을 하나 생성하고, 인덱스 i를 0으로 초기화합니다.
- i가 문자열 길이보다 작은 동안 다음을 반복합니다.
- s[i]가 ']'인 경우:
- 스택에서 요소를 꺼내며 대괄호 안에 있던 문자열만 추출합니다(res).
- n := 0으로 초기화합니다.
- 스택이 비어 있지 않고, 스택 최상단이 숫자라면 해당 숫자들을 조합하여 실제 정수 n을 만듭니다.
- j를 1부터 n까지 반복하면서 res의 각 문자(x는 0부터 res 크기까지)를 스택에 다시 삽입합니다.
- 그 외의 경우 s[i]를 스택에 삽입합니다.
- i를 1 증가시킵니다.
- s[i]가 ']'인 경우:
- 빈 문자열 ans를 생성합니다.
- 스택이 빌 때까지 스택 최상단 요소를 ans 앞에 붙이고 pop 합니다.
- ans를 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string decodeString(string s) {
stack <char> st;
int i = 0;
while(i<s.size()){
if(s[i] == ']'){
string res = "";
while(st.top()!='['){
res = st.top() + res;
st.pop();
}
st.pop();
int n = 0;
int x = 1;
while(!st.empty() && st.top()>='0' && st.top()<='9'){
n = n + (st.top()-'0')*x;
x*=10;
st.pop();
}
for(int j = 1; j <= n; j++){
for(int x = 0; x < res.size();x++){
st.push(res[x]);
}
}
}
else{
st.push(s[i]);
}
i++;
}
string ans ="";
while(!st.empty()){
ans = st.top() + ans;
st.pop();
}
return ans;
}
};
main(){
Solution ob;
cout << ob.decodeString("1[ba]2[na]");
}입력
"1[ba]2[na]"
출력
"banana"
코드 설명
위 구현의 핵심 로직은 다음과 같습니다.
- ']'를 만나면: 스택에서 '['가 나올 때까지 문자를 pop 하여 대괄호 내부 문자열(res)을 역순으로 재조립합니다. 이후 '['도 제거하고, 그 위에 쌓여 있는 숫자 문자들을 읽어 반복 횟수 n을 계산합니다. 자릿수 처리를 위해 x 변수를 사용해 1, 10, 100... 단위로 누적하는 방식입니다.
- 반복 삽입: 추출한 문자열 res를 n번 반복하여 다시 스택에 push 합니다. 이렇게 하면 중첩된 인코딩(예: "2[a2[b]]")도 올바르게 처리됩니다.
- 최종 결과: 모든 문자를 처리한 후, 스택에 남아 있는 문자들을 앞에서부터 조합하여 최종 디코딩 문자열을 완성합니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(N)에 비례합니다. 여기서 N은 디코딩된 최종 문자열의 길이입니다. 중첩된 패턴이 많아질 경우 출력 문자열의 크기가 기하급수적으로 커질 수 있으므로, 실제 실행 시간은 출력 크기에 좌우됩니다.