백준 3015_Python

https://www.acmicpc.net/problem/3015

3015번: 오아시스 재결합

문제

---

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

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

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

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

 

입력

---

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

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

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

 

출력

---

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

 

접근법

---

1.  문제에서 stack 을 활용하여, 푸는 문제이지만, 같은 수가 들어왔을 시에 어떻게 처리해줄 까 고민하던 문제이다.
2.  문제에서 stack 을 활용했을시, stack[-1]보다 큰 수가 들어오면, stack[-1]의 수는 더이상 오른쪽으로 보질 못하므로, 들어오는 수보다 작아질때까지, stack.pop()을 시켜준다.
3.  stack.pop()을 시킬때, stack[-1] 이 가지는 앞쪽으로 가지는 영향력을 ans에 더해주면 된다.
4.  같은 부분을 처리할때는 cnt 라는 항목에 +1 을 더해주어, 새로운 수가 앞쪽으로 가지는 영향력을 +1씩 해서 더해주었다.

 

n = int(input())

ans = 0
stack = []
# stack 의 추가 되는 수는 튜플형식(a.b) 인데, a 는 수를 나타내고, b는 앞자리까지의 영향력을 나타낸다.
for _ in range(n):
    h = int(input())
    # 스택의 제일 끝자리 보다 큰수가 들어왔을 시, stack[-1] 수의 앞자리 영향력을 더해준다.
    while stack and stack[-1][0] < h:
        ans += stack.pop()[1]

    if stack and stack[-1][0] == h:
        cnt = stack.pop()[1]
        ans += cnt
        # len(stack) 이 0 이 아니라면, stack 에 수가 들어왔을시,stack[-1]과 새로운 수의 관계를 더해준다.
        if len(stack) != 0:
            ans += 1 
        stack.append((h, cnt+1))
    else:
        # len(stack) 이 0 이 아니라면, stack 에 수가 들어왔을시,stack[-1]과 새로운 수의 관계를 더해준다.
        if len(stack) != 0:
            ans += 1
        stack.append((h, 1))

print(ans)