백준: 3015 오아시스 재결합

문제

3015번: 오아시스 재결합

 

문제 풀이

 N명이 한 줄로 서서 기다리고 있을 때, 볼 수 있는 사람의 수를 구하는 문제이다. 두 사람 A와 B가 서로 보기 위해서는 A, B 사이에 둘 보다 키가 큰 사람이 없어야 한다. 문제를 풀기 위해서는 `stack`을 활용하여, 현재 `top`보다 큰 키가 입력된다면, 이후에 입력되는 값은 현재의 `top`을 볼 수 없으므로 `pop`을 하여야 한다. 이와 반대의 경우 라면 `stack`에 추가한다. 주의해야 할 것은 연속된 동일한 숫자를 처리하기 위해 stack에 추가할 때 `(키, 연속된 횟수)`를 추가해주어야 한다.

 

코드

from sys import stdin


def solve():
    stack = []
    answer = 0

    for h in height:
        while stack and stack[-1][HEIGHT] < h:
            answer += stack.pop()[CNT]

        if not stack:
            stack.append((h, 1))
        else:
            if stack[-1][HEIGHT] == h:
                cnt = stack.pop()[CNT]
                answer += cnt

                if stack:
                    answer += 1

                stack.append((h, cnt + 1))
            else:
                stack.append((h, 1))
                answer += 1
    return answer


if __name__ == '__main__':
    HEIGHT, CNT = 0, 1
    n = int(stdin.readline())
    height = [int(stdin.readline()) for _ in range(n)]
    print(solve())