[백준/Python] 10773 제로

문제: https://www.acmicpc.net/problem/10773

 

 

사용 알고리즘: 스택

 

 

생각보다 너무너무 쉬웠던 문제!

같은 티어의 dp, dfs 문제들이 훨씬 어려웠던 느낌이다.

 

 

입력

• 첫 번째 줄에 정수 K (1 <= K <= 100,000)
• 이후 K 개의 정수가 주어짐

 

K 개의 정수가 주어졌을 때 0 이라는 정수가 나오면 바로 직전에 나왔던 정수를 지우면 된다. 

그래서 마지막에 남아있는 수들을 모두 더해서 결과를 내면 되는 간단한 문제

 

0을 만났을 때 가장 최근의 수를 지우면 된다? -> 바로 스택을 떠올렸다

스택은 LIFO(Last In First Out)으로 가장 마지막에 들어온 놈이 가장 먼저 나가는 자료구조

 

파이썬에서는 스택 자료구조를 따로 제공하지 않기 때문에 스택을 구현하기만 하면 아주 쉽게 풀 수 있는 문제다.

 

- 스택 알아보기

스택(stack), 큐(queue)

 

 

스택 구현하기

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        self.items.pop()

    def top(self):
        try:
            self.items[-1]
        except IndexError:
            print('Stack is empty')

    def __len__(self):
        return len(self.items)

 

 

0 만나면 최근에 들어온 숫자 지우기

• 0 만나면 가장 최근에 들어온 숫자 지움 -> stack.pop() 
• 0 이 아니면 스택에 넣기 -> stack.append(num)

stack = Stack()

for _ in range(k):
    num = int(input())
    if num == 0:
        stack.pop()
    else:
        stack.push(num)

 

 

 

전체 코드

import sys
input = sys.stdin.readline

# 스택 구현
class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        self.items.pop()

    def top(self):
        try:
            self.items[-1]
        except IndexError:
            print('Stack is empty')

    def __len__(self):
        return len(self.items)

# 입력
k = int(input())

# 스택 만들기
stack = Stack()

for _ in range(k):
    num = int(input())
    if num == 0:
        stack.pop()
    else:
        stack.push(num)

print(sum(stack.items))