[백준] 17298번 : 오큰수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1. 문제 설명

2. 풀이과정

N의 최대 크기가 1,000,000이므로 반복문을 사용해 오큰수를 찾으면 제한 시간을 초과하게 된다.

하여 스택을 활용해 문제를 해결하고자 한다.

 

오큰수가 존재하지 않는 수는 -1을 출력하므로 오큰수를 저장할 리스트를 -1로 초기화한다.

오큰수는 해당 수 다음 수들에서 찾아야 하므로 숫자들의 인덱스를 저장할 스택을 생성한다.

스택에 원소가 있고 스택의 제일 마지막 인덱스 위치의 값이 현재 인덱스 위치의 값보다 작으면(오른쪽에 있으면서 해당 값보다 큰 수 중 가장 왼쪽에 있는 수) 오큰수를 저장하는 리스트에서 스택의 제일 마지막 원소인 인덱스 위치에 해당 값을 저장한다.

현재 인덱스를 스택의 제일 마지막 원소로 추가한다.

해당 과정을 제일 마지막 인덱스까지 반복하며 오큰수를 구하고 구한 오큰수를 출력한다.

 

슈도코드

1. N(수열 개수) 입력받기
2. li 수열 리스트 채우기
3. answer(정답 리스트 -1로 초기화)
4. stack(스택 선언)
5. for i N만큼 반복
6. while (스택에 원소가 있고, 현재 수열 값이 top에 해당하는 수열보다 클 때까지)
7. 스택에서 pop한 값을 index로 하는 정답 리스트 부분을 수열 리스트의 현재 값(li[i])으로 저장
8. 스택에 i 값 저장 (현재 인덱스 추가)
9. 정답 리스트 출력

반응형

3. 소스코드

import sys

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

answer = [-1] * N
stack = list()

for i in range(N):
    while (stack and li[stack[-1]] < li[i]):
        answer[stack.pop()] = li[i]

    stack.append(i)

print(*answer)