[백준] 3015 - 오아시스 재결합 (P5)

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

3015번: 오아시스 재결합

개인적으로 플레 난이도 치고는 풀만한 문제라고 생각한다.

중복되는 키가 연속으로 들어오는 경우를 체크하는게 고민 포인트.

 

내가 푼 알고리즘은 다음과 같다.

 

0. 맨 처음에 들어오는 키는 그냥 스택에 넣는다.

 

1. 수를 입력받으면 해당 수와 스택의 탑에 있는 값을 비교한다.

 

    1.1 탑에 있는 값 > 새로 들어온 값 인 경우 (키가 감소)

        탑에 있는 값과 새로 들어온 값이 서로 보이므로 count += 탑에 있는 연속 카운트 값

 

    1.2 탑에 있는 값 == 새로 들어온 값 인 경우 (키가 같음)

        탑에 있는 값과 새로 들어온 값이 서로 보이므로 count += 탑에 있는 연속 카운트 값

        만약 이후에 더 큰 값이 들어오면 탑에 있는값과 새로 들어온 값 모두 새로 들어온 값과 서로 볼 수 있다.

        따라서 중복되는 값은 중복되는 값이 몇개나 있는지 별도로 같이 세서 스택에 저장한다.

        => 따라서 처음부터 스택에 키를 저장할 때, 해당 키를 가진 사람이 연속으로 몇 명 있는지도 저장한다.

        기존 탑에 있는 값을 pop 한뒤, 연속count를 +1 해서 다시 스택에 저장한다.

 

    1.3 탑에 있는 값 < 새로 들어온 값 인 경우 (키가 증가)

        새로 들어온 값이 새로 들어온 값보다 큰 동안 계속 pop 하면서 각 연속count만큼 count를 더해준다.

        만약 pop을 할 수 있을 때까지 다 했는데도 스택에 값이 남았다면 그 값은 새로 들어온 값보다 크니 서로 볼 수 있다.

        따라서 count += 1 한다.

        (이때는 연속 카운트 만큼 더하는게 아니라 1만 더하는 이유:

         => 연속하는 top 이전 값이 새로 들어온 값과 서로 볼 수 없다.  5 5 2 3 예시로 이해하면 된다.)

 

2. 이 과정을 반복한다.

 

알고리즘이 복잡하지 않아서 구현은 간단하게 된다.

import sys
input = sys.stdin.readline
n = int(input())
stack = [(int(input()),1)]
ans = 0
for _ in range(n-1):
    h = int(input())
    same_count = 1
    while stack and stack[-1][0] <= h:
        pop_h, count = stack.pop()
        if pop_h == h:
            same_count += count
        ans += count
    if stack:
        ans += 1
    stack.append((h, same_count))
print(ans)