[백준] 17298 오큰수 (Python)

문제

---

17298번: 오큰수

문제 풀이

---

해당 문제의 입력이 백만 개가 들어올 수 있으므로 O(N)만큼의 시간복잡도로 해결해야 하는 문제.

 

단순히 각 원소를 접근할 때 마다 오른쪽의 원소와 비교하며 오큰수를 발견 시 이를 출력하게 되면 

O(N^2)로 문제 해결이 되지 않는다.

 

따라서 문제 해결을 위해 다른 방법을 찾아야 했다.

 

필자는 다음과 같이 생각했다.

1) 오른쪽에 작은 수가 들어오게 되면 해당 수는 쓸모가 없는 수가 되는 것일까

2) 오른쪽에 큰 수가 들어오게 되면 이전 수에도 영향을 미치지 않을까

 

1)의 경우, 그렇다.

An보다 An+1이 작은 경우,

  An-1까지는

    An보다 작은 경우, An과 그 이전에서 출력이 될 것이고,

    An보다 큰 경우, An+1 이후에 나오는 수 중 해당 수보다 큰 수를 출력을 하게 된다.

 

2)의 경우에도 그렇다.

내림차순으로 수가 들어오다 큰 수가 들어오게 되면 앞선 수들에게도 영향을 끼치게 된다.

 

따라서 NGE 라는 배열을 -1로 초기화하고, 들어오는 수들을 차례대로 확인하면서 내림차순일 때는 stack에 추가하고, 마지막에 들어온 수보다 큰 경우 pop으로 해당 위치에 NGE 값을 덮어씌우면 될 것, 또한 앞선 수들과도 반복해서 비교를 해 줘야 한다.

 

 

 

코드

---

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

NGE = [-1 for _ in range(N)]
stack = [0]
for i in range(1, N):
    while stack and A[stack[-1]] < A[i]:
        NGE[stack.pop()] = A[i]
    stack.append(i)
print(*NGE)