[백준] 17289 오큰수 (python)

1) [백준] 17289 오큰수 (python)

문제 출처 : 

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

 

2) 문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

만약 A 가 [9 8 7 6 5 4 3 2 1 ] 일 경우 9의 오큰수를 찾기 위해 마지막 인덱스까지 찾아야한다.

이 때 시간복잡도가 매우 높아지기 때문에 시간제한에 걸린다.

시간복잡도가 약 N/2인데 크기가 1,000,000일 때 시간복잡도가 1억을 넘어가기 때문이다.

 

따라서

A가 [3 5 2 1 8 10] 일 경우

거꾸로 3을 오큰수로 갖는 인덱스 없으므로 패스

5를 오큰수를 갖는 앞의 인덱스는 3 

이 때 3의 오큰수를 5로 지정

2를 오큰수를 갖는 앞의 인덱스 없으므로 패스 

1도 패스 

8의 경우 앞의 1,2,5보다 크므로 1,2,5 의 오큰수로 지정 

10의 경우 앞의 8의 오큰수이므로 8의 오큰수로 지정

10 의 경우 맨마지막이므로 -1 

근데 이렇게 해도 시간 복잡도가 넘어간다.

1,2,5의 경우 8의 오큰수를 중복으로 갖는 것을 확인할 수 있다.

따라서 스택을 사용하면 시간복잡도를 줄일 수 있다.

 

정리 !

스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.

오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에는 -1를 출력한다.

 

- 문제 푸는 순서 

1) 스택이 채워져 있고 A[index](오큰수)>A[top] 의 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장한다. pop은 조건 만족 시 계속 반복한다 

2) 현재 인덱스를 스택에 append하고 다음 인덱스로 넘어간다.

3) 1번,2번을 수열 길이만큼 반복 후 스택에 남아있는 인덱스는 -1을 저장한다.

 

수열 리스트 A

index.    0 1 2 3

value.    3 5 2 7 

 

1) 스택이 비어있으므로 무조건 append()

myStack = [0] #수열의 값이 아닌 index를 저장 

 

결과 

index.    0 1 2 3

value                 

 

2) A[0] < 5  # 3<5 

pop()으로 오큰수 저장. 데이터 append

myStack[0(pop),1(append)]

 

index.    0 1 2 3

value     5. # 더 이상 A[0]은 아무처리도 안해도 되므로 시간복잡도가 줄어듬

 

3) A[1] > 2 5>2 

데이터 append()

myStack[1,2(append)]

 

index.    0 1 2 3

value.    5 

 

4) A[2] < 7 , A[1] < 7 

pop()으로 오큰수 저장, 데이터 append() 

myStack[1(pop),2(pop),3(append)]

 

index.    0 1 2 3

value.    5 7 7 

 

5) 수열의 길이만큼 반복 후 스택에 남아있는 index에 -1 저장

myStack[3(pop)]

 

index.    0 1 2 3

value.    5 7 7 -1 

 

 

 

3)소스  코드

import sys
n = int(input())
ans = [0] * n  #정답 배열, n 크기 만큼 만들어주기
A = list(map(int,sys.stdin.readline().rstrip().split())) #수열 리스트
myStack = [] #스택 선언

for i in range(n) :
    # 스택이 비지않고 현재 수열값이 top에 해당하는 수열보다 클 때 까지
    while myStack and A[myStack[-1]] < A[i] :  #오큰수 조건
        ans[myStack.pop()] = A[i] #정답 리스트에 오큰수 저장
    myStack.append(i)

while myStack: #스택이 없어질때까지
    ans[myStack.pop()] = -1

for i in ans :
    print(i,end=' ')