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

백준 - 3015 오아시스 재결합

 

 

문제

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

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

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

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

입력

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

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

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

출력

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

 

 

문제해결방법- 서칭 참고

 

 

이 문제는 백지 상태에서 떠올리기 힘든 것 같다.

 

 

 

d[ i ]가 왼쪽의 볼 수 있는 사람을 카운팅하는 개념이다. '쌍'의 수를 구하는 것이라 결국 총합은 같다.

 

1) 스택에 들어갈 때 4, 5번 인덱스처럼 키가 같다면 4번이 스택에서 빠져도 같은 사람들 수가 누적되어 카운팅되도록 cnt 에 += 1 를 해준다. 키가 같은 사람이 없다면 cnt 는 1씩 기록되는 거다.(cnt가 2인 사람이 있다면 그 앞의 같은 키의 사람은 스택에서 이미 빠져나갔기 때문에 이 걸 반영하는 거다.)

 

2) 큰 키는 스택에서 더 큰 키를 만나기 전에는 빠지지 않는다. 고로 스택에 마지막까지 빠지지 않고 남아있는 사람은 큰 키다. ans[ i ]에 추가로 += 1 를 해야 한다. 3, 7번의 사람은 앞의 큰 키를 가진 사람만 본다. 반대로 앞의 키가 작거나 같은 사람들은 스택에서 빠지게 된다.

 

 

 

-코드

import sys
input = sys.stdin.readline

n = int(input())
d = [int(input()) for _ in range(n)]
stack = [[0, 0]]
ans = [0 for _ in range(n)]

for i in range(n):
    cnt = 1
    while stack and stack[-1][0] <= d[i]:
        lth, cnt = stack.pop()
        if lth < d[i]:
            ans[i] += cnt
            cnt = 1
        elif lth == d[i]:
            ans[i] += cnt
            cnt += 1
    if stack:
        ans[i] += 1
    stack.append([d[i], cnt])
    
print(sum(ans))

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
d = [int(input()) for _ in range(n)]
stack = [[0, 0]]
ans = [0 for _ in range(n)]

for i in range(n):
    while stack and stack[-1][0] < d[i]:
        lth, cnt = stack.pop()
        ans[i] += cnt
    if stack and stack[-1][0] == d[i]:
        lth, cnt = stack.pop()
        ans[i] += cnt
        if stack:
            ans[i] += 1
        stack.append([d[i], cnt+1])
    elif stack and stack[-1][0] > d[i]:
        ans[i] += 1
        stack.append([d[i], 1])
    if not stack:
        stack.append([d[i], 1])

print(sum(ans))