[Python] 파이썬 백준(17298) 오큰수

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

17298번: 오큰수

---

---

스택 문제 이긴 하지만 어떻게 풀어도 O(n^2)의 시간복잡도가 나올 거라는 생각에 for문을 2개 사용해서 문제를 해결하고자 했다..!

import sys
input = sys.stdin.readline

n = int(input())
nge_list = list(map(int, input().split()))
answer = []

for i in range(n):
    for j in range(i,n):
        if j == n-1 and nge_list[i] >= nge_list [j]:
            answer.append(-1)

        if nge_list[i] < nge_list [j]:
            answer.append(nge_list [j])
            break

answer = map(str, answer)
print(' '.join(answer))

역시,,, 안될거 같았지만 도전하는 정신이 중요하다고 생각한다. 어쨌든 시간 초과가 떴다.

stack을 통해 접근하기로 하고 아래와 같이 구조를 작성했다.

---

i번째 원소는 그 바로 다음 수 보다 크기 때문에 s에 들어가게 된다.

 

그다음 i+1와 i+2를 비교할 때 i+1보다 i+2가 작다면 i보다도 당연히 작게 된다.

i+1보다 i+2가 크다면 i+1 자리에 i+2를 넣고 i와 비교한다 (stack 사용)

 

위와 같은 방법을 따르면 for문을 2번 돌지 않아도 되기에 시간이 빠르다.

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
answer = [-1]*n
stack = [0]

for i in range(1,n):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)

print(*answer)