백준 / 오큰수 / 17298번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 오큰수 / 17298번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/17298

 

문제 설명

---

나의 풀이

N = int(input())

# 리스트
NGE = list(map(int, input().split()))
# 결과 값을 담을 스택
stack = []

for i in range(0, N - 1):
    stack.append(NGE[i])
    for j in range(i + 1, N):
        if stack[-1] < NGE[j]:
            stack.pop()
            stack.append(NGE[j])
            break
        if j == N - 1:
            stack.pop()
            stack.append(-1)

stack.append(-1)

print(' '.join(map(str, stack)))

스택을 이용해서 앞에 있는 숫자들을 하나씩 펼쳐보면서 나아가는 방식을 사용했다.

이 풀이의 문제점은 시간 복잡도가 O(N^2)가 발생할 수 있다는 것이다.

N = int(input())

# 리스트
NGE = list(map(int, input().split()))

# 결과를 저장할 리스트, 초기값은 -1로 설정
result = [-1] * N

# 스택, 저장할 값은 (NGE[i], i)
stack = []

# 역순으로 탐색
for i in range(N - 1, -1, -1):
    # 스택에서 현재 NGE[i]보다 작은 값들을 제거
    while stack and stack[-1] <= NGE[i]:
        stack.pop()

    # 스택이 비어있지 않다면, 오큰수를 결과에 기록
    if stack:
        result[i] = stack[-1]

    # 현재 값을 스택에 추가
    stack.append(NGE[i])

# 결과 출력
print(' '.join(map(str, result)))

반대로 뒤에서 시작을 하면 시간 복잡도를 O(N)까지 줄일 수 있다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/40

[자료구조] 스택(Stack)