[CodingTest] BOJ17298 오큰수 ( 자료구조 ) With 파이썬

17298번: 오큰수

 

 

◎ 문제풀이

 

단순 반복문으로 풀면 시간초과가 난다. 자료구조로 시간복잡도를 줄일 수 있는 능력을 보는 문제이다. 

 

[CodingTest] BOJ1046 에디터 ( 자료구조 ) with Python

( 위 문제도 자료구조로 시간복잡도를 줄이는 문제이니 참고바란다. )

 

 

자신보다 큰 가장 오른쪽에 있는 수를 출력하는 문제이다.

 

 

 

 

5의 오큰수를 구해보자. 5의 가장 오른쪽은 2이다. 2는 5보다 작으므로 오큰수가 아니다.

 

 

 

그렇다고 바로 옆의 수를 탐색하면 안된다. 이는 시간복잡도 O(N)이다. 우리는 O(N)이 아닌 O(1)로 문제를 해결해야 한다. 5의 오큰수를 구하지 못했으니 5를 잠시 KEEP 해두어야 한다. 호출된 순서대로 잠시 KEEP하는 자료구조는 STACK이다.

 

 

 

 

STACK의 top은 바로 POP 될수 있는 수이다. 5는 잠시 2 밑에 KEEP해두고 2와 2의 오른쪽 수인 7를 비교한다. 7은 2보다 크므로 2의 오큰수는 7이 된다. 그럼 KEEP 해둔 5를 꺼낼 차례이다.

 

 

 

7은 5보다 크므로 5의 오큰수는 7이 된다. 

 

이처럼 STACK은 '기억' 기능을 갖고 있기에, O(N)으로 탐색하지 않고 잠시 KEEP해둘 수 있다.  STACK에 잠시 저장하므로써 바로 옆에만 비교하는 O(1)의 시간복잡도가 가능해진다. 

 

 

◎ 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split())) # 수열 테이블
result = [-1] * (n) #결과 테이블

stack = [] #스택테이블
stack.append(0) # 인덱스를 STACK에 저장
i = 1 # 오큰수 포인터

while stack and i < n :
  while stack and  arr[stack[-1]] < arr[i] : # 오큰수인 경우
    result[stack[-1]] = arr[i]  # 결과저장
    stack.pop() # STACK에서 제거 
    
  stack.append(i) # 다음 인덱스 STACK에 추가
  i += 1 # 오큰수 포인터 이동

#출력
for value in result :
  print(value, end=" ")