[백준] 3015 - 오아시스 재결합 (Python)

---

앞에서부터 한 명씩 차례대로 줄을 선다고 생각하면 스택을 사용할 수 있다. 서로 볼 수 있어야 하므로, 모든 사람들은 오직 앞쪽만 본다고 가정해도 무리가 없다. 스택은 항상 키의 내림차순으로 정렬되어 있다.

키가 작은 사람이 줄을 서면 스택에 넣는다.

키가 큰 사람이 줄을 서면 그 앞의 모든 작은 사람들은 뒤에서 볼 수 없으므로 스택에서 제거한다.

키가 같은 경우를 효율성을 고려해서 같은 키가 연속으로 등장하면 한 묶음으로 구현한다.

---

import sys
input = sys.stdin.readline

n = int(input())
stack = []
count = 0
for _ in range(n):
    height = int(input())
    while stack:
        if stack[-1][0] < height:
        # 키가 큰 경우
            count += stack[-1][1]
            stack.pop()
            # 반복적으로 앞사람의 수를 카운트하고 스택에서 제거
        elif stack[-1][0] == height:
        # 키가 같은 경우
            count += stack[-1][1]
            if len(stack) > 1:
                count += 1
                # 자신보다 키가 큰 사람 1명을 더 볼 수 있다
            stack[-1][1] += 1
            # 앞의 묶음에 추가된다
            break
        else:
        # 키가 작은 경우
            count += 1
            # 바로 앞 사람 1명을 볼 수 있다.
            stack.append([height, 1])
            # 스택에 넣는다.
            break
    if not stack:
        stack.append([height, 1])
    
print(count)