[백준] 17298번 with Python (아직 못품)

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

알고리즘 기초 1/2의 문제들을 풀던 중에 풀이 자체는 간단하지만 접근하는게 어려웠던 것 같아 글을 적어봅니다. 처음에는 정말 단순하게 리스트로 비교를 해서 문제를 풀면 되지 않을까라고 접근을 했었기 때문에 무작정 리스트로 문제를 풀었습니다. 

import sys
input = sys.stdin.readline
# import operator
# import time
input = sys.stdin.readline

N = int(input())


t = list(map(int, input().split()))

a = list()
# start = time.time()
while(len(t)!=0):
    i = t[0]
    # print(t)
    for j in t:
        if i < j:
            del t[0]
            a.append(str(j))
            break;
        if j == t[len(t)-1]:
            a.append(str(-1))
            del t[0]
print(*a)

계속 문제에 대한 답을 제출해도 틀리고 또 틀리고를 반복하다가 질문검색에서 여러 설명을 보다 보니 애초에 접근을 잘못했었던 점을 알게 되었습니다. 일단 시간초과가 나는 이유를 찾아보니 del 라는 함수의 시간 복잡도는 O(N) 그리고 for문을 써주게 되면서 결국엔 O(N^2)으로 문제를 계속 풀고 있으니 시간 복잡도는 터지고 답은 나오겠지만 시간안에 그 답을 못 내줘서 계속 틀린다는 것을 알게 되었습니다.

해결을 하려면 결국 시간을 줄여야 되고 일단 del 함수 등과 같은 시간이 드는 요소 들을 정리해보기로 했습니다. 

import sys
input = sys.stdin.readline

N = int(input())

t = list(map(int, input().split()))

a = list()
k=0
while(k!=N):
    i = t[k]
    j = 0
    for y in range(k,N):
      j = t[y]
      if i < j:
          a.append(str(j))
          break;
      j = -1
    if j == -1:
      a.append(str(j))
    k += 1
print(*a)

위의 코드가 어느정도 정리를 했을 때 모습인데 해당 답도 결국엔 봤던 곳을 다시 본다는 점에서 시간을 더 잡아 먹고 있는 문제가 있습니다. 스택을 리스트를 통해서 쓰려고 하다가 스택의 개념을 아예 적용안하고 있지 않나 라는 생각이 계속 들어서 다시 스택에 넣고 빼는 과정을 그리면서 생각을 해봤습니다.