[leetcode][394] Decode String

문제 : leetcode.com/problems/decode-string/

---

k[encoded_string] 의 룰을 가진 문자열이 주어진다. 이 룰은 encoded_string 문자열을 k번 반복한다는 뜻이다.

룰은 중첩되서 나올 수 있다. k는 반드시 숫자이며 encoded_string에는 숫자가 포함되지 않는다.

위 룰을 적용한 문자열이 주어질 때 decode한 결과를 구하라.

---

괄호? => 스택. 백퍼는 아니지만 대부분의 문제에 적용된다.

k와 encoded_string을 pair로 가지는 스택을 만든다.

이 때 입력 문자열을 "3[a]"라 하였을 때 이는 "1[3[a]]" 와 동일하기 때문에 코드의 일관성을 맞춰주기 위해(예외처리 덜하려고. ex. "ab3[a]" 와 같은 문자열은 초기에 나오는 ab를 스택에 값이 없는지 판단 후 answer에 추가하거나 해야함) 초기 스택에 (1, "")을 넣고 시작했다.

문자열의 탐색이 끝났을 때 스택에는 우리가 추가한 1[ encoded_string ] 에 대한 정보만 남아있을 것이고  이 때 encoded_string이 정답이 된다.

 

문자열의 문자로 분기를 탈 수 있는 경우는 총 4가지이다.

1. 숫자

  cnt 변수(k)를 만들어서 이를 갱신한다. cnt = 10 x cnt + 현재 탐색중인 문자가 나타내는 숫자.  

2. 여는 괄호 [

  스택에 (cnt, "")을 넣는다.

  cnt 변수를 0으로 초기화.

3. 닫는 괄호 ]

  스택의 top에 있는 정보로 문자열을 decode한 뒤 pop 한다.

  decode 결과(encoded_string을 k번 반복한 문자열)를 스택의 top에 있는 인코딩된 문자열 뒤에 추가한다.

  ex) s = "3[a4[b]]" 이고 빨간색 닫는 괄호를 탐색중일 때 스택에는 [{4,"b"},{3,"a"},{1,""}]가 저장되어 있을 것이다. ({1, ""} 는 우리가 임시로 넣어준 요소.)

        top에 있는 {4, "b"} 정보로 "bbbb" 라는 디코딩된 문자열을 구하고 pop 했으면 이를 "a" 뒤에 추가한다.

        결과 스택은 다음과 같다. [{3, "abbbb"},{1,""}]

4. 이외 = 인코딩된 문자

  stack의 top에 있는 인코딩 문자열 뒤에 탐색중인 문자를 추가한다.

 

시간복잡도는 O(N). N = 입력 문자열 길이.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/394.%20Decode%20String.cpp