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

플레5 문제인 오아시스 재결합 문제이다.

 

스택을 사용하여 문제를 풀었다.

 

겁도 없이 플레5 문제를 풀게 되었는데 스택을 사용한다는 것을 알고 있으니 생각보다는 괜찮았던 것 같다.

(몇 시간 걸리긴 했지만)

 

확실히 Java 보다는 Python이 좀 더 간편한 것 같다.

자바로 푼 건 파이썬으로, 파이썬으로 푼건 자바로 풀어봐야겠다.

 

# 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
# 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램
import sys

# 입력 N(1 <= N <= 500,000) <- O(N^2) <= 시간 복잡도 <= O(NlogN)
# 출력: 서로 볼 수 있는 쌍의 수 출력
input = sys.stdin.readline

N = int(input().rstrip())

stack = []

result = 0

# 키가 내림차순일 경우 stack에 계속 쌓음
for i in range(N):
    num = int(input().rstrip())
    pair = [num, 1]
    
    # 내림차순의 가장 작은 값과 새로 들어온 값을 비교해서 새로운 값이 크다면
    # 자신보다 큰 사람이 나올때까지 볼 수 있다.
    # 만약 동일한 키가 존재한다면 다음 사람에게 저장해 놓음.
    while stack and stack[-1][0] <= num:
        pop = stack.pop()
        result += pop[1]
        if num == pop[0]:
            pair[1] += pop[1]
	
    # 내림차순일 유지될 경우 stack에 값이 남아있음
    # 따라서, 인접한 내림차 순 사람쌍은 볼 수 있으므로 결과값 증가
    if stack:
        result += 1

    stack.append(pair)

print(result)