[백준] - PATRIK(3015)

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

3015번: 오아시스 재결합

풀이시간

설계: 160분 구현: 20분

문제 종류

스택, 자료구조

풀이 방법

이 문제의 요구사항은 다음과 같이 정의된다.

 

1. 두개의 인덱스를 결정한다. (A,B)

2. 두개의 인덱스 사이에 있는 값들은 arr[A] > val and arr[B] > val 을 동시에 만족해야한다.

 

예를들어 배열이 4,2,3,5 와 같은 형태의 경우 가능한 쌍은 아래와 같다

(4,2),(4,3),(2,3),(3,5),(5,4)

 

가능한 쌍의 형태를 보면 알 수 있듯이 본인과 인접한(인덱스 길이 차이가 1) 숫자와의 쌍은 반드시 형성될 수 있고

ex) (4,2) (2,3) (3,5)

인덱스 차이 길이가 2이상인 숫자에 대해서는 아래와 같이 정의될수 있다

현재 위치가 i 일경우 i-1 ... 0 중 본인보다 작거나 같은 숫자의 개수 + (만약 본인보다 큰 수가  존재하면 1)

 

A 를 시작점 B 를 끝점이라고 할때 만약 arr[B] 가 5면 (4,5), (3,5) 만 가능하고 (2,5) 는 불가능하다.

(2,3) 단계에서 2는 이미 3보다 작은 숫자기 때문에 5입장에서는 2를 포함하면 안된다.

코드

N = int(input())
arr = [0]
ans = 0
st = []
for i in range(N):
    num = int(input())
    arr.append(num)
for i in range(1, N + 1):
    if len(st) == 0:
        st.append((i, 1))
        continue
    if arr[i] < arr[st[-1][0]]:
        st.append((i, 1))
        ans += 1
    else:
        cnt = 0
        next_i = 1
        while len(st) and arr[i] >= arr[st[-1][0]]:
            vi, ccnt = st[-1][0], st[-1][1]
            val = arr[vi]
            cnt += ccnt
            if val == arr[i]:
                next_i = ccnt + 1
            st.pop()
        if len(st) > 0:
            cnt += 1
        ans += cnt
        st.append((i, next_i))

print(ans)