[백준] 오큰수

출처::  www.acmicpc.net/problem/17298

분류:: 스택

 

1. 문제 이해 및 해결과정

- n의 숫자로 보았을 때, 이중 for문으로 풀면 시간초과 날 것이고, O(N),O(logN)을 고민해 봐야 한다 - 스택의 인덱스를 이용하여 push,pop한다.  1. stack의 인덱스를 순차적으로 이용한다  2. stack에 수가 있고, 현재 배열이 스택의 탑보다 크면 스택의 탑을 빼서(인덱스) 결과 인덱스 배열에 넣는다 3. 스택에 인덱스는 항상 추가한다.

 

2. 풀이방법

  1. 스택

#오큰수
#https://www.acmicpc.net/problem/17298
import sys
sys.stdin = open("input.txt","r")
n=int(input())
#O(logN) O(N) O(1)로 풀어야함
arr = list(map(int, sys.stdin.readline().split()))
stack = []
result= [-1 for _ in range(n)]

for i in range(len(arr)): #인덱스를 이용
    while stack and arr[stack[-1]]<arr[i]: #오큰수 라면
        #현재 스택의 top이 arr[i]보다 작다면
        result[stack.pop()]=arr[i] #stack.pop()이 인덱스, result의 인덱스에 최대값
    stack.append(i)
print(*result)

 

3. 오답원인

 

4. 알게된 점

배열의 인덱스를 이용해서 스택 구현

 

리스트 한 번에 출력하기 

print(*result)