[baekjoon]python #17298 오큰수

[baekjoon]python #17298 오큰수

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

😫시간초과

N = int(input())
arr = list(map(int,input().split()))

result = []

for i in range(N):
    Max_V = -float('inf')
    for j in range(i+1,N):
        if arr[i] < arr[j]:
            Max_V=max(Max_V,arr[j])
            break
        else:
            Max_V=-1
    if i == N-1:
        Max_V=-1
    result.append(Max_V)

print(*result)

이중 for문을 사용해서 풀었는데 예제 답은 잘 나오지만 O(n^2)의 시간복잡도라 시간 초과가 났다...

 

 

😀문제 해결

N = int(input())
arr = list(map(int,input().split()))
answer = [-1]*N
stack=[]

for i in range(N):
    while stack and (stack[-1][0] < arr[i]):
        temp,idx = stack.pop()
        answer[idx]=arr[i]
    stack.append([arr[i],i])
print(*answer)

이 풀이도 O(n^2)를 갖는 코드이지만 첫번째 코드처럼 다 비교하는게 아니라 필요한 부분까지만 비교해서 통과가 된 거 같다. 

 

😮다른 사람 코드

import sys
input = sys.stdin.readline

n = int(input())
seq = list(map(int,input().split()))
stack = []

for i in range(n):
    while(stack):
        if seq[i] > seq[stack[-1]]:
            seq[stack.pop()] = seq[i]
        else:
            stack.append(i)
            break
    
    if not stack:
        stack.append(i)
for i in stack:
    seq[i] = -1
    
print(*seq)