쿠폰 코드 연쇄 정리

자바스크립트 코딩테스트 문제로 stack-queue 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium stack-queue 함수명: solution 제한 시간: 200ms

문자열 code가 주어질 때, 서로 같은 문자가 연속으로 붙어 있으면 즉시 함께 제거되는 규칙을 반복 적용한 뒤 최종적으로 남는 문자열을 반환하는 solution 함수를 작성하세요.

예를 들어 ABCCBA는 가운데 CC가 먼저 제거되고, 그 결과 ABBA가 되며, 다시 BB, AA가 차례로 제거되어 최종 결과는 빈 문자열이 됩니다.

제한사항

code는 대문자 알파벳으로만 이루어진 문자열입니다.
code의 길이는 0 이상 100,000 이하입니다.
같은 문자가 인접해 있으면 반드시 제거해야 합니다.
제거가 일어난 뒤 새롭게 인접해진 같은 문자도 계속 제거해야 합니다.
최종적으로 남은 문자열을 반환하세요. 아무 문자도 남지 않으면 빈 문자열 ""을 반환합니다.

예시

입력: "ABCCBA" → 출력: ""
입력: "CABBADEED" → 출력: "C"
입력: "AABBCCDDX" → 출력: "X"

힌트

문자열을 왼쪽부터 보면서, 지금까지 남아 있는 문자들만 따로 관리해 보세요.
새 문자가 들어올 때 가장 마지막에 남아 있는 문자와만 비교하면 됩니다.
매번 문자열 전체를 다시 탐색하면 길이가 길 때 비효율적일 수 있습니다.

해설

이 문제의 핵심은 연쇄 제거를 효율적으로 처리하는 것입니다.

단순하게 생각하면, 연속된 같은 문자를 하나 제거할 때마다 문자열을 다시 이어 붙이고 처음부터 검사할 수 있습니다. 하지만 이 방식은 제거가 많이 일어나는 경우 매우 비효율적입니다.

더 좋은 방법은 스택처럼 동작하는 배열을 사용하는 것입니다.

문자열을 왼쪽부터 한 글자씩 확인합니다.
스택의 맨 위 문자와 현재 문자가 같다면, 두 문자는 서로 제거되어야 하므로 스택에서 꺼냅니다.
같지 않다면 현재 문자를 스택에 넣습니다.
모든 문자를 처리한 뒤 스택에 남은 문자들을 이어 붙이면 정답입니다.

예를 들어 CABBADEED를 보면:

C → 스택: C
A → 스택: CA
B → 스택: CAB
B → 마지막 B와 같으므로 제거 → 스택: CA
A → 마지막 A와 같으므로 제거 → 스택: C
D → 스택: CD
E → 스택: CDE
E → 제거 → 스택: CD
D → 제거 → 스택: C

최종적으로 C만 남습니다.

이 방식은 각 문자가 스택에 한 번 들어가고 많아야 한 번 나오므로 시간 복잡도는 O(n)입니다. 길이가 긴 문자열도 충분히 처리할 수 있습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.