중첩 반복 문자열 펼치기
자바스크립트 코딩테스트 문제로 nested-string-decoding 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
압축된 문자열 code가 주어집니다.
문자열 안에는 k[문자열] 형태의 반복식이 들어갈 수 있습니다. 이는 대괄호 안의 문자열을 k번 반복한다는 뜻입니다.
반복식은 서로 중첩될 수 있습니다. 예를 들어 3[a2[c]]는 안쪽의 2[c]가 먼저 cc가 되고, 바깥쪽에서 acc를 3번 반복해 accaccacc가 됩니다.
압축을 모두 풀어 완성된 문자열을 반환하는 decodeNestedRepeatString 함수를 작성하세요.
제한사항
0 <= code.length <= 100000code는 영문 소문자, 숫자,[,]로만 이루어져 있습니다.- 입력으로 주어지는 반복식은 항상 올바른 형식입니다.
- 반복 횟수
k는1이상100이하의 정수이며 여러 자리일 수 있습니다. - 숫자는 항상 바로 뒤에
[가 오는 반복 횟수로만 등장합니다. - 최종 결과 문자열의 길이는
100000이하입니다.
예시
- 입력:
code = "3[a]2[bc]"-> 출력:"aaabcbc" - 입력:
code = "3[a2[c]]"-> 출력:"accaccacc" - 입력:
code = "2[ab3[c]]x"-> 출력:"abcccabcccx" - 입력:
code = "10[z]"-> 출력:"zzzzzzzzzz" - 입력:
code = "plain"-> 출력:"plain"
힌트
[를 만나면 지금까지 읽은 반복 횟수와 현재까지 만든 문자열 조각을 잠시 보관해 보세요.]를 만나면 현재 조각을 반복해서 직전 문자열 뒤에 붙이면 됩니다.- 여러 자리 숫자를 처리하려면 숫자 문자를 만날 때마다
num = num * 10 + digit형태로 누적할 수 있습니다.
해설
이 문제는 중첩 구조를 안쪽부터 먼저 풀어야 하므로 스택을 쓰면 자연스럽게 해결할 수 있습니다.
문자열을 왼쪽부터 읽으면서 현재 만들고 있는 문자열 조각을 current, 방금 읽고 있는 반복 횟수를 count라고 둡니다.
숫자를 만나면 count에 누적합니다. [를 만나면 지금까지의 current와 count를 하나의 프레임으로 스택에 저장하고, 안쪽 문자열을 새로 만들기 위해 current를 빈 문자열로 바꿉니다.
]를 만나면 현재 조각 하나가 완성된 것입니다. 스택에서 직전 프레임을 꺼내고, current.repeat(반복 횟수)를 이전 문자열 뒤에 붙입니다. 이렇게 하면 가장 안쪽 반복식부터 차례대로 완성되어 바깥 반복식에 자연스럽게 포함됩니다.
예를 들어 3[a2[c]]를 보면 a를 읽은 뒤 2[c]가 먼저 cc로 풀리고, 현재 조각은 acc가 됩니다. 마지막 ]에서 이 조각을 3번 반복해 최종 답을 얻습니다.
각 문자는 한 번씩 읽고, 완성된 문자열 조각만 필요한 만큼 붙이므로 시간 복잡도는 최종 출력 길이를 포함해 O(n + 결과 길이)입니다. 스택에는 열려 있는 반복식만 저장되므로 공간 복잡도는 O(n + 결과 길이)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.