2841-외계인의 기타 연주

https://www.acmicpc.net/problem/2841

2841번: 외계인의 기타 연주

 

처음 딱 읽었을 때 풀이방법이 떠오르지 않았다. 왜 스택 생각이 안났을까.. 알고리즘 분류를 먼저 보고 풀었다면 고민도 안하고 풀 문제였어서 아쉬웠다..

 

풀이방법은 간단하다. 기타의 각 줄마다 스택을 만들어 놓고 새로 누를 줄이 스택의 상단보다 작으면 pop을 해나가는 식으로 체크를 하면 된다. 이미 누르고 있는 프렛이 입력으로 또 주어질 수 있다는 점만 주의하자..!

import sys
input = sys.stdin.readline
N, P = map(int, input().split())
stack = [[] for _ in range(N+1)]
ans = 0
for _ in range(N):
    l, p = map(int, input().split())
    while len(stack[l]) > 0:
        if stack[l][-1] > p:
            stack[l].pop()
            ans += 1
        else:
            break
    if len(stack[l]) == 0 or stack[l][-1] != p:
        stack[l].append(p)
        ans += 1

print(ans)