[Python][백준] 17298번 오큰수

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

공부 날짜 : 2023.01.31
정답 참조 여부 : X

현재 값을 기준으로 오른쪽에 있는 수 중에 자신보다 크고 가장 가까운 수를 구하고 만약 없다면 -1을 출력하는 문제이다.

---

가장 마지막 숫자는 항상 -1이라는 점에서 오른쪽에서 부터 오큰수를 찾아가는데 바로 오른쪽의 수가 자신의 오큰수면 바로 값을 스택에 쌓고

그게 아니라면 오큰수 스택에서 탐색하도록 했다.(이미 다음 수 중에서 자신보다 큰수가 탐색되었기 때문)

별로 어려움 없이 정답이 나왔긴 했는데 최악의 경우 시간복잡도가 O(N^2)이기 때문에 시간 초과가 날 줄 알았더니 그냥 정답이 나왔다. 채점 과정에서도 시간이 상당히 오래걸렸고 아슬아슬하게 깬거 같아서 좀 더 찾아봤다.

추가로 찾아본 정답은 스택으로 수를 쌓아가다가 오큰수를 찾으면 스택에서 값을빼고 정답에 오큰수를 입력해주는 방식이였다.

처음에 같은 방법을 떠올리긴 했는데 O(N^2)라고 생각해서 시도안한 방법인데 정답이라고 알고 다시 계산하니 O(N)이였다.

---

시간복잡도 계산이 아직 익숙하지가 않다 2중 for을 쓰게되면 항상 곱하게 되는데 이번 문제는 단순히 2N이 되기에 나보다 빠른 코드였던것이다.

시간 복잡도 계산이 아직 익숙하지 않다고 느끼고 있다. 알고리즘을 생각하며 시간복잡도를 잘 생각해봐야겠다.

소스코드

import sys
input_ = sys.stdin.readline
#########################################
n = int(input())
input_data = list(map(int, input_().split()))

# 값 비교를 위한 최대값 출력시 -1로 바꿔서 출력
INF = 1000001

# 정답이 역순으로 저장되는 리스트
NGE = [INF]
# 역순으로 탐색, 마지막 값은 무조건 -1이므로 생략
for index in range(n-2, -1, -1):
    # 다음 값과 비교해서 다음 값이크면 바로 NGE에 추가
    if input_data[index] < input_data[index + 1]:
        NGE.append(input_data[index + 1])

    # 아니면 NGE에서 역순으로 보며 자신보다 큰 수 추가
    else:
        for i in range(len(NGE)-1, -1, -1):
            if input_data[index] < NGE[i]:
                NGE.append(NGE[i])
                break


# 역순으로 출력
for i in range(n-1, -1, -1):
    if NGE[i] == INF:
        print(-1, end = " ")
        continue

    print(NGE[i], end = " ")