17298번 오큰수(DP,Backtracking) Python

동기

친구들이랑 같이 PS하다가 잘 못풀길래 저장해둡니다 :)

문제정의

입출력

간단한 생각 정리

먼저 오큰수 개념은 쉽네요. 오른쪽에 있는 나보다 큰 수중 제일 가까이 있는 수입니다.
이 때!
수 $A_1 A_2 ... A_iA_{i+1}...A_n$이 존재한다고 해봅시다. 일단 우리는 오큰수라는 개념을 생각할 때 Case들을 나눠볼 수 있겠죠.

$A_i$에 대해 생각해봅시다.
Case1. 만약 $A_{i+1}$이 $A_i$보다 크다면 당연히 $A_{i+1}$은 $A_i$의 오큰수입니다. Easy하네요.

Case2. 만약 $A_{i+1}$이 $A_i$보다 크지않다면? $A_{i+1}$의 오큰수가 $A_{i}$의 오큰수가 될 가능성이 있다 정도로 생각하면 되겠네요.  

 

만약 Case2.에서 $A_{i+1}$의 오큰수가 $A_k$라고 해봅시다.(-1일 수도 있겠죠.) 이 때 $A_i$의 오큰수가 $A_k$일 수도 있고 아닐 수도 있습니다. 만약 아니라고 해보죠. 그러면 다시 $A_k$의 오큰수를 볼 수 있습니다. $A_t$라고 해보죠.

또 작으면 또 그의 오큰수, 그의 오큰수를 본다고 생각합시다. 우리는 결국 -1이거나 $A_i$의 오큰수를 찾을 수 있을겁니다.

구현방법

위의 생각을 구현하려면 $A_i$의 오큰수를 구할 때 $A_{i+1}...A_n$까지의 모든 오큰수를 알고 있어야합니다.
그러면 이는 수학의 strong induction과 같은 것이고 DP로 구현할 수 있습니다.

그러면 뒤의 정보는 어떻게 알 수 있죠? 간단합니다. 뒤에서부터 반복문을 돌리면 됩니다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 쉽죠? $A_n$의 오큰수는 -1입니다. 그다음엔 $A_{n-1}$,$A_{n-2}$들을 차례로 값을 구해주면 되겠습니다.

시간복잡도

위의 방법이 합리적인 방법일까요? worst case를 만들어 생각해보아야겠습니다.

$10 \ 9 \ 8\ 7\ 6\ 5\ 4\ 3\ 2\ 1$

위의 case는 worst case일까요? 아닙니다. 예를들어 10의 오큰수를 9로부터 가져올 때 9의 오큰수는 -1이므로 바로 -1로 가지게 됩니다.
다른 숫자도 그렇습니다.

$10 \ 1 \ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9 \ 10 \ 11$

요런경우는 어떨까요? $A_0$을 제외하고는 다 1번의 연산 $A_0$만 n번 연산입니다. 이때도 대충 2n번이면 연산이 끝나네요.

대체 어떻게 해야 worst case를 얻어낼 수 있을까요?

사실 잘 모르겠습니다. 운영체제 과제하러 가야해요...여백의 시간이 부족해서 남겨두겠습니다.
근데 거의 느낌상 $O(n)$입니다.
절대 $O(n^2)$은 안나올거라고 확신했고 잘 안돼도 $O(n\sqrt n)$일겁니다.

소스코드

import sys

N = int(input())

A = list(map(int,sys.stdin.readline().split()))

B = [0 for i in range(N)]

B[N-1] = (-1,-1)

for i in range(N-2,-1,-1):
    if(A[i]<A[i+1]):
        B[i] = (A[i+1],i+1)
    else:
        check = B[i+1]
        while(A[i]>=check[0] and not check[0] == -1):
            check = B[check[1]]

        B[i] = check

for idx,val in enumerate(B):
    print(val[0],end=' ')