백준 3015 오아시스 재결합 (파이썬)

풀이 및 해설(주석)

import sys

N = int(sys.stdin.readline().strip())
S = []
rst = 0
for _ in range(N):
    hei = int(sys.stdin.readline().strip())
    
    # 스택이 있고 그 스택의 마지막의 키가 나보다 작으면 그 수를 pop과 rst에 +
    # pop하는 경우는 나와 이어지는 경우임
    while S and S[-1][0] < hei:
        rst += S.pop()[1]
        
    # 스택이 빈 경우 그냥 넣어주기
    if not S:
        S.append([hei, 1])
        
    # 스택의 마지막 키가 나와 같은 경우, 일단 pop해서 그 수를 rst에 더해주고
    elif S and S[-1][0] == hei:
        cnt = S.pop()[1]
        rst += cnt
        
        # 이때 스택이 남아있다면, 나와 그 스택안의 값이 이어지므로 +1
        if S:
            rst += 1
        
        # 내 키와 현재 그 키의 수를 +1해서 스택에 append
        S.append([hei, cnt + 1])
        
    # 스택이 비어있지 않고, 위의 조건에 만족하지 못할 때, 내 키와 수=1 을 추가하고 rst에 1추가(나와 스택안의 이어짐)
    else:
        S.append([hei, 1])
        rst += 1

print(rst)

 

---

후기

• 지금까지 푼 스택 문제들과 비슷하면서 살짝 관점이 달라서 그걸 이해하는데 시간이 좀 걸린 문제
• 처음에는 while문을 돌리며 그냥 작으면 더해주면 되지 않나 싶었지만, while S and S[-1] <= hei
• 이렇게 되면 예를 들어 4, 1, 2, 2, 5 이런 식으로 키가 있으면,
• 5차례에서 2를 두 번 볼 수 있어야 되는데 2를 한 번 밖에 볼 수가 없음
• 그래서, 같은 키일 때 따로 처리를 해줘야되는 문제