야구 게임 점수 기록기가 있다고 가정해 보겠습니다. 문자열 리스트가 하나 주어지며, 각 문자열은 다음 네 가지 유형 중 하나입니다.
- 정수 (한 라운드의 점수) − 해당 라운드에서 얻는 점수를 나타냅니다.
- "+" (한 라운드의 점수) − 해당 라운드의 점수가 최근 두 개의 유효한 라운드 점수의 합임을 의미합니다.
- "D" (한 라운드의 점수) − 해당 라운드의 점수가 바로 이전 유효 라운드 점수의 두 배임을 의미합니다.
- "C" (연산자, 라운드 점수가 아님) − 직전 유효 라운드의 점수가 무효화되었으며 제거해야 함을 의미합니다.
여기서 중요한 점은 각 라운드의 연산이 영구적(permanent)이라는 것입니다. 즉, 하나의 연산이 이전 라운드와 이후 라운드 모두에 영향을 줄 수 있습니다. 우리가 구해야 하는 값은 모든 라운드에서 얻을 수 있는 점수의 총합입니다.
예시로 이해하기
입력이 ["5","2","C","D","+"]라고 한다면, 출력은 30이 됩니다. 과정을 단계별로 살펴보면 다음과 같습니다.
- 라운드 1 − 5점을 획득합니다. 누적 합계: 5
- 라운드 2 − 2점을 획득합니다. 누적 합계: 7
- 연산 1 ("C") − 라운드 2의 점수가 무효화되어 제거됩니다. 누적 합계: 5
- 라운드 3 ("D") − 직전 유효 점수(5)의 두 배인 10점을 획득합니다. 누적 합계: 15
- 라운드 4 ("+") − 최근 두 유효 점수의 합인 5 + 10 = 15점을 획득합니다. 누적 합계: 30
문제 해결 접근 방식
이 문제는 스택(Stack) 자료구조를 사용하면 깔끔하게 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- 빈 스택(stack)을 생성합니다.
- ops 리스트의 각 요소 i에 대해 다음을 반복합니다.
- i가 "+"라면: 스택의 마지막 두 요소(first, second)를 꺼내 그 합을 스택 끝에 삽입합니다.
- i가 "D"라면: 스택의 마지막 요소에 2를 곱한 값을 스택 끝에 삽입합니다.
- i가 "C"라면: 스택의 마지막 요소를 삭제합니다.
- 그 외의 경우(정수): 해당 값을 정수로 변환해 스택 끝에 삽입합니다.
- 반복이 끝나면 스택에 남아 있는 모든 요소의 합을 반환합니다.
스택을 사용하는 이유는 "C" 연산으로 이전 점수를 제거하거나, "+", "D" 연산으로 최근 점수를 참조해야 하기 때문입니다. 스택의 마지막 요소에만 접근하면 되므로 시간 복잡도는 O(n)으로 매우 효율적입니다.
파이썬 구현 코드
class Solution:
def calPoints(self, ops):
stack = []
for i in ops:
if i == "+":
first, second = stack[len(stack) - 1], stack[len(stack) - 2]
stack.append(first + second)
elif i == "D":
stack.append(stack[-1] * 2)
elif i == "C":
stack.pop()
else:
stack.append(int(i))
return sum(stack)
ob = Solution()
print(ob.calPoints(["5","2","C","D","+"]))
입력
["5","2","C","D","+"]
출력
30
이처럼 스택의 특성(LIFO, 후입선출)을 활용하면 점수의 추가, 삭제, 참조 연산을 모두 간단하게 처리할 수 있습니다. 코딩 테스트에서 자주 등장하는 대표적인 스택 활용 문제이므로, 위 코드를 직접 실행해 보며 동작 원리를 익혀두는 것을 추천합니다.