내 코드
거꾸로 시작하는 방식을 사용하여서 arr[i]값과 stack의 top값을 비교하였다.
만약 top값이 현재값보다 크다면 바로 printStk에 넣으면 되지만, 바로 큰 값을 못 찾을 수도 있기 때문에 큰 값을 찾을때까지 pop하면서 찾는다.
문제에서 N <= 1,000,000 이기 때문에 최악의 경우를 생각 했을 때
배열이 {백만 , 999999 , ... 1 } 이런 경우를 생각하면 시간초과가 나게된다.
(1000000 + 999999 + .... + 1) 번 해야함
이문제는 시간 안에 풀 수 있는 방법을 찾지 못하였다.
다른사람 풀이
뒤에서부터 하지 않고 앞에서 부터 함.
수열이 계속 작아지다가 계속 커지는 형태 ↘↗ 이런형태 가지면 최악인데 위에 방식보다는 훨씬 작음
순서의 차이에서도 시간이 다를 수 있다.
여기서 top-down , down-top 중 어느것을 택할지도 고려해야하는 것을 알게됨
ㅋ