[Stack] Daily Temperatures

T라는 daily temperatures가 주어질때, 그 다음 더 큰 온도(warmer temperature)는 몇개의 원소뒤에 나오는지를 value로 표현한 배열을 리턴하라는 뜻이다.

예컨데 [ 70, 71, 65]라면 70보다 큰 온도인 71은 1회, 71,65보다 큰 온도는 아예 나오지 않았으므로 0회이므로 [1, 0, 0]으로 표현된다.

 

우선 결과배열을 만들고 T의 길이만큼 0으로 채워주는 값을 디폴트로 정한다

이중For문을 이용하여 일일이 돌릴수도 있지만, 연산하지 않아도 되는 원소는 연산하지 않기 위해 Stack을 사용하였다.

앞에 나온 원소는 뒤에서 비교할 필요가 없으므로 Stack에 넣어주는 것이다.

 

지속적으로 인접한 원소의 크기를 비교해주는 방식이다.

stack에 index들을 넣어두고, index에 위치한 온도보다 높은 온도를 찾았을때만 answer로 넘겨주는 방식이다.

 

예컨데 i=2의 경우는, stack에 1이 담겨있고, i=2의 온도가 i=1의 온도보다 큰것이 맞으므로 Answer[1]을 2-1의 값으로 지정해주면 된다.

또한 i=3의 경우는, stackt에 2가 담겨있지만 i=3의 온도가 i=2의 온도보다 크지 않으므로 stack에 3을 추가로 담아 [2,3]의 stack을 만든다.

따라서 Answer[2]는 해당 Loop에서 정해지지 않는다.

 

이는 조금 더 복잡한 i=5에서 해결되는데, 이 시점에는 stack에 2,3,4가 담겨있다

이때 i=5와 i=4를 비교했을때 5가 더 크므로 Answer[4]가 정해지고, stack에는 여전히 2,3이 남아있기때문에 연쇄적으로 각각과 비교하게 된다.

이 과정에서 Answer[3], Answer[2]가 정해지게 된다. 한번 빠져나간 stack의 원소는 다시 들어올일이 없다.