[백준 알고리즘] 17298번 : 오큰수 (Python) 문제 풀이

문제

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

 

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

17298번: 오큰수

문제 풀이 :

solved.ac에 올라온 난이도 골드4 문제 치고는? 쉬운 편이었다.

간단한 자료구조 스택을 이용한 문제였다.

 

문제 부터 이해해보자.

크기가 N인 수열(배열)이 주어지고, 왼쪽부터 차례대로 기준이 되는 숫자의 오른쪽에 있는 수중에 가장 큰 수를 출력한다.

 

나는 처음에는 for문과 if문을 사용하였는데, 시간초과로 인해서 계속 틀리게 되었고

이에 자료구조를 조금 바꾸어 deque를 이용한 Stack를 사용하였다.

 

배열에 순서대로 값을 넣은뒤

맨 앞에서부터 차례대로 스택에 넣는다. 이후에 만약에 stack[-1][0] 보다 num_list[i]가 더 크다면

모든 수를 스택에서 pop한 뒤에 모든 indx의 값을 num_list[i]로 바꾸는 것이다.

이후에 다시금 num_list를 차례대로 진행하면서 다시 stack에 push한다.

 

내 코드 : 

from collections import deque

num = int(input())
num_list = [int(x) for x in input().split()]
answer = [-1] * num
stack = deque()

for i in range(num) :
    while stack and (stack[-1][0] < num_list[i]) :
        tmp, indx = stack.pop()
        answer[indx] = num_list[i]
    stack.append([num_list[i],i])

print(*answer)