Python으로 스택 연산을 순서대로 처리한 뒤 최종 결과 확인하기

문자열로 이루어진 리스트 ops가 있다고 가정해 보겠습니다. 이 리스트의 각 요소는 아래 연산 중 하나입니다.

음수가 아닌 정수 값 — 해당 숫자를 스택에 push합니다.
"POP" — 스택의 맨 위(top) 요소를 삭제합니다.
"DUP" — 맨 위 요소를 한 번 더 삽입하여 복제합니다.
"+" — 맨 위 두 개의 요소를 pop한 뒤, 그 합을 다시 push합니다.
"-" — 맨 위 두 개의 요소를 pop한 뒤, (맨 위 요소 − 그 아래 요소)의 결과를 push합니다.

모든 연산을 차례대로 수행한 후, 스택의 맨 위에 남아 있는 요소를 구해야 합니다. 만약 중간에 유효하지 않은 연산이 나오면(예: 빈 스택에서 POP을 수행하는 경우) -1을 반환합니다.

예시 동작 과정

입력이 ops = ["5", "2", "POP", "DUP", "3", "+", "15", "-"]라고 해보겠습니다. 이때 출력은 7이 됩니다.

처음 두 연산으로 5와 2를 push → 스택: [5, 2]
POP으로 하나 제거 → 스택: [5]
DUP으로 5를 복제 → 스택: [5, 5]
3을 push → 스택: [5, 5, 3]
"+" 연산 적용 → 스택: [5, 8]
15를 push → 스택: [5, 8, 15]
"-" 연산 적용 → 스택: [5, (15 − 8)] = [5, 7]

따라서 최종적으로 스택의 맨 위 요소는 7입니다.

문제 해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

새로운 스택을 생성합니다.
ops의 각 요소 i에 대해 반복합니다.
- i가 숫자라면 스택에 push합니다.
- 스택 크기가 1 이상이고 i가 "POP"이라면 맨 위 요소를 제거합니다.
- 스택 크기가 1 이상이고 i가 "DUP"이라면 맨 위 요소를 꺼낸 뒤(p), 같은 값을 두 번 push합니다.
- 스택 크기가 2 이상이고 i가 "+"라면 두 요소를 꺼내(a, b) 합(a + b)을 push합니다.
- 스택 크기가 2 이상이고 i가 "-"라면 두 요소를 꺼낸 뒤(a, b) 차이(a − b)를 push합니다.
- 그 외의 경우에는 -1을 반환합니다.
모든 연산이 끝나면 스택의 맨 위 요소를 반환합니다.

구현 예제

아래 코드를 통해 더 잘 이해할 수 있습니다.

def solve(ops):
    stack = []
    for i in ops:
        if i.isnumeric() == True:
            stack.append(int(i))
        elif len(stack) >= 1 and i == "POP":
            stack.pop()
        elif len(stack) >= 1 and i == "DUP":
            p = stack.pop()
            stack.append(p)
            stack.append(p)
        elif len(stack) >= 2 and i == "+":
            a = stack.pop()
            b = stack.pop()
            stack.append(a + b)
        elif len(stack) >= 2 and i == "-":
            a = stack.pop()
            b = stack.pop()
            stack.append(a - b)
        else:
            return -1
    return stack.pop()

ops = ["5", "2", "POP", "DUP", "3", "+", "15", "-"]
print(solve(ops))

입력

["5", "2", "POP", "DUP", "3", "+", "15", "-"]