17298번 오큰수

문제링크 : www.acmicpc.net/problem/17298

17298번: 오큰수

 

---

---

 

버전 1. 입력을 stack에 받고, 복사한 stack temp을 이용하여 stack의 top이 temp의 top보다 큰지 확인(시간초과)

stack = []
def push(L,a):
    L.insert(0,a)
def pop(L):
    del L[0]
def top(L):
    return L[0]
def size(L):
    return len(L)
import sys
N = int(sys.stdin.readline())
stack = list(map(int,sys.stdin.readline().split()))

index = 0
for _ in range(N):
    now = top(stack)
    pop(stack)
    temp = []
    if(size(stack)==0):
        print(-1,end =' ')
    else:
        while(size(stack)!=0):
            if(top(stack)>now):
                break
            else:
                push(temp,top(stack))
                pop(stack)
        if(size(stack)!=0):
            print(top(stack), end= ' ' )
        else:
            print(-1, end=' ')
        while(size(temp)!=0):
            push(stack,top(temp))
            pop(temp)

 

버전 2. 오큰수를 찾지 못한 수의 index를 stack에 저장해놓고 for문을 돌며 오큰수 찾기(시간초과)

def push(L,a):
    L.insert(0,a)
def pop(L):
    del L[0]
def top(L):
    return L[0]
import sys
N = int(sys.stdin.readline())
numbers = list(map(int,sys.stdin.readline().split()))
answer = [-1 for _ in range(N)]

temp = []
for i in range(0,N):
    while((len(temp)!=0) and (numbers[top(temp)]<numbers[i])):
        answer[top(temp)] = numbers[i]
        pop(temp)
    push(temp, i)

for item in answer:
    print(item, end = ' ')

 

버전 3. 함수로 이동하면서 소요되는 시간을 줄이고자 버전2를 함수 없이 만든 버전(메모리:153476KB 시간 : 1632ms)

import sys
N = int(sys.stdin.readline())
numbers = list(map(int,sys.stdin.readline().split()))
answer = [-1 for _ in range(N)]
stack = [0]

i = 1
while(stack and i<N):
    while(stack and (numbers[stack[-1]]<numbers[i])):
        answer[stack[-1]] = numbers[i]
        stack.pop()
    stack.append(i)
    i+=1

for item in answer:
    print(item, end = ' ')