백준 17298번 오큰수 문제 파이썬 풀이

오큰수 

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

48250

16000

11599

32.571%

문제

크기가 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)을 공백으로 구분해 출력한다.

예제 입력 1 복사

4
3 5 2 7

예제 출력 1 복사

5 7 7 -1

예제 입력 2 복사

4
9 5 4 8

예제 출력 2 복사

-1 8 8 -1

 

 

 

시작하기 앞서 

 

 

엄청 많이 틀렸었다.. 

분명 주피터 노트북에서 실행했을 때는 잘 됐는데 계속 틀렸다고 뜸

퍼센트도 안 뜨고 바로 저렇게 뜰 때가 제일 착잡하더라..

왜였을까?  찾아보니

 

 

import sys
input=sys.stdin.readline

n=int(input())
number=list(map(int,input().split()))
nge=[-1]*n
stack=[]

for i in range (n):
        while stack and number[stack[-1]]<number[i]:
            nge[stack.pop()]=number[i]
        stack.append(i)
        

print(*nge)

일단 이게 정답 코드! 

저기서 list(map(int, input().split()))이라고 적었는데

원래 코드에서는 map과 int를 빼먹었던 것 

그래서 틀렸다고 떴던거였음...!

 

 

알고리즘의 핵심은 스택에 인덱스를 넣어 활용하는 것이다. 

먼저 nge에 -1 -1 -1 -1 이렇게 n만큼 넣어준다 

 

1. for i in range (n)안에서 반복한다 

2. 스택이 비어있지 않고, number(스택의탑) <number(i)일 때 

nge[stack.pop()]에 number[i]를 넣어주어 -1과 값을 교체한다. 

 

stack.pop()을 하면 스택의 탑에 해당하는 원소 값이 들어가고, pop된다. 

while문은 스택이 비어있지 않을 때까지 하기 때문에, 두 개 이상의 nge에도 값을 넣을 수 있다 

while문을 건너뛰었다는 건 더 큰 숫자를 못 만났다는 뜻이기에 기다렸다가 같이 넣어주는 거임! 

ex) 결과값 5 7 7 -1의 7 7과 -1 8 8 -1의 8 8 

 

 

 

 

해답을 보고 풀었지만 

노트에 알고리즘을 어떻게 작성할 건지 적어보니 도움이 많이 됐다. 

교수님이 하루에 하나씩 알고리즘 문제를 풀면 된다고 하셨다. 

조금 늦은 감이 있지만.. 늦었다고 생각했을 때가 가장 빠른 때니까 열심히 하자!!