[파이썬] 백준 17298번 오큰수

문제 확인

---

17298번: 오큰수

• 시간 제한 : 1초
• 메모리 제한 : 512MB

나의 풀이

---

시간 제한이 1초, 수열의 길이가 1,000,000이기 때문에 시간 제한에 걸리지 않으려면  $O(N), O(Nlog_{N})$의 시간 복잡도 정도로 문제를 해결해야 했다. 따라서 2중 for문으로 모든 경우를 조회하는 경우는 고려하지 않았다.

 

어떤 방식으로 크기와 위치를 동시에 고려할 수 있을까 고민하다가, 결국 원소가 아닌 index를 stack에 넣어서 해결할 수 있었다.

import sys

n = int(input())
seq = list(map(int, sys.stdin.readline().rstrip().split()))
# nge_list : 초기값 -1로 설정
output_list = [-1] * n
# idx 저장 stack
stack = []

for i in range(n):
	# 현재 idx 처리 전
    while stack:
    	# 이전 위치의 값 보다 큰 수가 나왔을 때 오큰수를 저장
        # 현재 위치의 값과 Stack 내 idx와 비교
        if seq[i] > seq[stack[-1]]:
            output_list[stack.pop()] = seq[i]
        else:
            break
    # 현재 idx 저장
    stack.append(i)

print(*output_list)

 

다른 사람 풀이

---

오른쪽 성분부터 순회하는 방식으로 풀었다. 이 경우 Stack에 어떤 값을 제거하고, 유지할 것인지가 중요하다.

아래 그림에서 왼쪽의 경우 A, B는 모두 다른 수의 오큰수가 될 수 있다. 하지만 오른쪽의 경우 B는 C의 존재 때문에 다른 수의 오큰수가 될 수 없다. 

전체 과정을 그림으로 나타내면 다음과 같다.

[스택] BOJ17298 오큰수 문제 풀이 및 전체 코드(C++)