17298: 오큰수

단계별 풀이 중 스택에 있는 가장 고난이도 문제이다.

스택 분류에 있는 문제라서 스택을 써야한다는 점을 알고 문제에 접근했지만

처음에는 스택 없이도 풀 수 있을 것 같다는 생각에 스택을 사용하지 않고 시도했다.

하지만 어김없이 시간초과를 받아버렸고.. 내가 짠 코드를 보니 O(N^2)으로 동작하는 코드였다.

N이 1,000,000 까지 들어오기 때문에 시간초과를 받기 쉬운 코드였다.

 

시간초과인 이유는 간단하다.

만약 입력이 1 1 1 1 1 1 1 . . . 2 이런식으로 들어올 경우 오큰수를 찾기 위해 최악의 경우인 제일 끝에 있는 2를 계속해서

찾아야한다는 점에서 효율성이 상당히 떨어진다.

이걸 모든 1에 대해서 반복해야하니 1이 많을수록 오래걸릴 수 밖에 없다.

 

이렇게 이중반복문과 투포인터까지도 사용해보면서 다양한 삽질을 해본 결과..

스택을 활용해보았는데 처음에는 스택을 어떻게 써야하는지 감을 못잡았다. (이게 삽질을 했던 이유..)

 

그러던 중 index를 기반으로 스택을 활용하는 방법에 대해서 찾게 됐다.

(참고 블로그: https://st-lab.tistory.com/196)

 

핵심 알고리즘은 주어진 수열을 순회하면서 stack의 top과 비교를 하고 만약 top보다 큰 숫자가 들어온다면

현재 숫자가 top보다 작을 때 까지 pop을 반복하며 해당 index에 위치한 값을 현재 순회 중인 큰 수로 바꿔준다.

반대로 top 보다 작다면 stack에 push를 해주면 된다.

순회를 마치고 stack에 남은 값은 오큰수가 없는 값이기 때문에 해당 index의 값을 -1로 바꿔주면 정답이 된다.

 

내가 놓쳤던 부분은 stack의 top과 비교를 해야한다는 부분이었다.

top을 활용하게 되면 현재 순회 중인 값 보다 작은 값까지 모두 오큰수가 되기 때문에 훨씬 구현이 간단해진다.

 

n = int(input())
seq = list(map(int, input().split()))
 
stack = list()
 
for i in range(len(seq)):
  if len(stack) == 0 or seq[stack[-1]] >= seq[i]:
    stack.append(i)
  else:
    while seq[stack[-1]] < seq[i]:
      idx = stack.pop()
      seq[idx] = seq[i]
 
      if len(stack) == 0:
        break
    stack.append(i)
 
for st in stack:
  seq[st] = -1
 
print(*seq)