3015. 오아시스 재결합

업데이트 시간 : 2023-04-06 15:29:53 +0000

[Platinum V] 오아시스 재결합 - 3015

문제 링크

성능 요약

메모리: 116012 KB, 시간: 444 ms

분류

자료 구조, 스택

문제 설명

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 2³¹ 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

💡 Solutions

📄 오아시스 재결합.py

N = int(input())
ans = 0

stack = list()

for _ in range(N):
    height = int(input()) # 현재 들어오는 사람의 높이
    
    people = (height, 1) # 사람의 높이를 저장
    
    while stack and stack[-1][0] <= height: # 스텍이 있고 마지막 스텍에 있는 사람의 높이가 현재 사람보다 작을 경우에
        ans += stack[-1][1] # 같은 높이의 사람의 수를 카운팅함.(이렇게 작업하면 같은 숫자를 반복해서 사용할 필요가 없다.....)
        if stack[-1][0] == height: # 사람의 높이가 같을경우
            people = (height, people[1] + stack[-1][1]) # 사람이 함녕 더 있다고 카운팅을 한다.
        stack.pop() # Stack에 들어가있는 사람은 현재 사람보다 작거나 같기 때문에 카운팅 할 필요가 없음.
        
    if stack: # 스텍이 살아 있을 경우에는 쌍이 무조건 하나 생김 (사람이 있기 때문에)
        ans += 1
    stack.append(people)
print(ans)