240312 [BOJ/백준] 17298. 오큰수

 

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

17298번: 오큰수

---

나의 코드

1. 이중 for문 (시간초과)

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

# ans = -1
for i in range(N):
    ans = -1
    for j in range(i+1, N):
        if arr[i] < arr[j]: # 오른쪽 큰 수가 있을 때 출력하고 브레이크
            ans = arr[j]
            break

    print(ans)

 

2. 스택에 인덱스를 이용한 풀이 (성공)

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

check = [-1]*N
stack = [0]

for i in range(1, N):
    while stack and arr[stack[-1]] < arr[i]:
        check[stack.pop()] = arr[i]
    stack.append(i)

print(*check)

 

결과

---

이중 for문으로 가볍게 문제를 풀었는데 시간초과가 됐다. readline으로 읽는 속도를 빠르게 하면 시간초과 문제를 해결할 수 있지 않을까 했는데 그것도 안됐다. 스택으로 한번만 돌게끔 했더니 PyPy보다 속도가 느린 Python으로도 시간문제를 해결할 수 있다는게 너무 신기하다. 문제를 어떻게 푸느냐에 따라 결과가 달라진다는 것을 깊이 체감할 수 있는 문제였다.