문제

풀이

처음에 이 문제를 의식의 흐름대로 생각해보면,

끝에서부터 앞으로 가면서 제일 처음 만나는 수 중 자신보다 큰 수의 인덱스를 저장하는 방법인데

이 방법대로 한다면 이중 for문을 돌려야 한다.

그러나 n이 500,000이기 때문에 시간초과가 되므로 다른 방법을 찾아야한다!

바로 스택을 이용하는 방법이다.

스택이 비어있다면, 스택에 인덱스와 값을 넣는다.

비어있지 않다면, 스택의 탑이 값보다 작으면 다 pop시킨다.

그래서 비어있으면 push하고, 아니면 스택의 탑에 있는 인덱스 값을 정답 배열에 알맞게 저장해놓는 것이다.

6 9 5 7 4 로 예를 들면,

순서 : (1, 6)

stack :

-> 처음에 스택이 비어있으므로 push 한다. 정답배열=[0, 0, 0, 0, 0]

순서 : (2, 9)

stack : (1, 6)

-> 스택의 탑의 값(stack.top().second)이 9보다 작으므로 pop을 할 것이다.

순서 : (2, 9)

stack :

-> 비어있으니까 push

순서 : (3, 5)

stack : (2, 9)

-> 스택의 탑의 값이 5보다 크니까 정답 배열을 stk.top().first로 갱신. 정답배열=[0, 0, 2, 0, 0]

이런식으로 쭉 해나가면 된다.