[스택] 코딩테스트 문제 TIL (제로) - 백준 10773번

1. 오늘의 학습 키워드

• 스택

---

2. 문제: 백준 10773번. 제로

• 단계: 🥈실버 4단계
• 주제: 구현, 자료 구조, 스택
• 출처: https://www.acmicpc.net/problem/10773

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

예제 입력 1 복사

4
3
0
4
0

예제 출력 1 복사

0

예제 입력 2 복사

10
1
3
5
4
0
0
7
0
0
6

예제 출력 2 복사

7

힌트

예제 2의 경우를 시뮬레이션 해보면,

• [1]
• [1,3]
• [1,3,5]
• [1,3,5,4]
• [1,3,5] (0을 불렀기 때문에 최근의 수를 지운다)
• [1,3] (0을 불렀기 때문에 그 다음 최근의 수를 지운다)
• [1,3,7]
• [1,3] (0을 불렀기 때문에 최근의 수를 지운다)
• [1] (0을 불렀기 때문에 그 다음 최근의 수를 지운다)
• [1,6]

합은 7이다.

---

3. 문제 풀이

Step1. 문제 이해하기

재민이는 재현이가 부르는 숫자를 써내립니다. 그런데 재현이가 0이란 수를 부를때는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓰는 상황입니다.

이 상황에서 재민이가 최종적으로 적어 낸 수의 합을 구하는 문제입니다.

문제의 입출력 및 제약 조건을 살펴보도록 하겠습니다.

• Input:
  • 첫 번째 줄에 정수 K가 주어집니다. K의 범위는 1이상 $10^5$이하입니다.
  • K의 값이 시간 복잡도에 영향을 줄 것입니다. 10^5이하이므로 $O(n^2)$보다 효율적인 시간 복잡도로 코드를 구성해야 합니다.
  • 이후 K개의 줄에 정수가 1개씩 주어집니다.
• Output:
  • 재민이가 최종적으로 적어 낸 수의 합을 출력합니다.

Step2. 문제 분석하기

이 문제는 대놓고 스택을 활용하라는 문제로 이해할 수 있습니다. 문제에 정수가 0일 경우에는 가장 최근에 쓴 수를 지우라고 나와있습니다. 즉, LIFO에 적합하죠!

따라서 스택 자료구조에 숫자를 넣다가 0이 나오면 스택 자료구조에서 값 한 개를 pop하면 됩니다.

사실상 코드 설계까지 완료됐습니다. 바로 코드를 구현해 보도록 하겠습니다.

Step3. 코드 구현

import sys
k = int(sys.stdin.readline().strip())
stack = []
for _ in range(k):
    data = int(sys.stdin.readline().strip())
    if data == 0:
        stack.pop()
        continue
    stack.append(data)
print(sum(stack))

• 코드 설명:
  • k = int(sys.stdin.readline().strip()): 입력으로 주어진 정수 k를 읽어들입니다. 이는 이후에 입력받을 정수의 개수를 의미합니다.
    
  • stack = []: 스택 자료구조를 구현하기 위해 리스트를 초기화합니다.
    
  • for _ in range(k):: k개의 입력을 반복적으로 처리합니다.
    
  • data = int(sys.stdin.readline().strip()): 현재 입력값을 읽어 data 변수에 저장합니다.
    
  • if data == 0:: 입력값이 0인 경우, 스택에서 가장 최근에 추가된 값을 제거(pop())합니다.
    • 스택 자료구조는 LIFO(Last In, First Out)이므로, 가장 마지막에 추가된 값을 제거합니다.
  • stack.append(data): 입력값이 0이 아닌 경우, 해당 값을 스택에 추가합니다.
    
  • print(sum(stack)): 최종적으로 스택에 남아있는 값들의 합을 출력합니다.
    • 스택에 남아있는 값은 모두 유효한 숫자들로, 더한 값이 최종 결과가 됩니다.
• 시간 복잡도:
  • 입력 처리: 입력받은 정수 개수 k만큼 반복문을 실행하므로 $O(k)$.
    
  • 스택 연산: 각 입력값에 대해 append 또는 pop을 한 번 수행하므로, 스택 연산의 시간 복잡도는 $O(1)$입니다. 이를 k번 반복하므로 전체 시간 복잡도는 $O(k)$.
    
  • 최종 합 계산: 스택에 남아있는 값의 합을 구하는 연산은 $O(n)$입니다. 여기서 n은 스택에 남아있는 원소의 개수로, 최악의 경우 $n = k$입니다. 따라서 최종 시간 복잡도는 $O(k)$입니다.
    
• 결과:

---

4. 마무리

이번 문제는 스택 자료구조의 기본적인 활용법을 다룬 문제로, "가장 최근에 추가된 값을 제거"해야 하는 요구 사항을 통해 스택의 LIFO 특성이 자연스럽게 적용되는 것을 확인할 수 있었습니다. 스택에 값을 추가하거나 제거하는 연산은 모두 O(1)의 시간 복잡도를 가지므로, 입력 크기 $k$에 대해 전체적인 시간 복잡도는 O(k)로 효율적인 해결이 가능했습니다. Python 리스트를 사용해 간결하게 스택을 구현할 수 있었으며, 스택 자료구조가 문제의 조건과 직관적으로 연결될 때 얼마나 효과적인지 다시 한번 깨달았습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!