Daily Temperature

생각해보자

• int nums = {73, 74, 75, 71, 69, 72, 76, 73 }
• 온도가 높아지는 시점을 찾아라?
• 오늘의 온도보다 낮아질 때 그 날의 온도가 기준점이 된다?
• 오늘의 온도보다 높다면 기준날의 온도와 차를 구한다?
• stack 을 이용한다
• 두 개를 비교해서 하나를 어딘가에 저장을 해야한다.
• 온도가 커진 날을 체크해야 한다?
• 74 에서 73 을 뺀다 = 1번방에서 0 방을 뺀다?

이번 알고리즘은 난이도가 있구나 ,, 하지만 오늘 내가 이해하고 만다. 차근차근히!

 

이런 배열이 하나 준비되어 있다.

 

 

 

 

 

 

 

답을 구하기 위해 만든 함수로 배열을 실어 보내자.

 

 

 

 

 

 

일단 답을 담을 그릇 하나를 준비하고

 

 

 

 

 

 

 

 

 

 for 문을 배열의 길이만큼 돌려주자

 

 

 

 

 

 

 

 

 

 

while 문을 실행하기 위한 조건은

•  stack 이 비어있지 않아야 헤
• 그리고 지금 내가 비교하려는 값과 stack top 값을 꺼내서 비교를 한다
• 지금 내가 비교하는 값이 더 크다면 while 문을 실행한다.
• 하지만 처음에는 비어 있을테니 실핼할 수 없다.

 

 

첫번째 73을 가진 0번째는 while문을 돌지 못하고

 

stack 에 push 된다.

stack 에 0번을 저장

 

 

 

 

 

 

 

i 가 1 일 때, 즉 74

while 이 true이다.

 

stack이 null이 아니고

 

temper[stack.peek] => temper[0]

이랑

temper[1] 을 비교한다.

 

73 < 74 true

 

 

 

stack 에 0이 들어있었잖아.

pop 해서 index에 넣어줘

 

현재 index 값 0

 

 

 

 

 

 

 

 result 배열에 [ index ] 번째에다가

i - index 값을 넣어준다.

 

즉 1 - 0 = 0

 

 

 

 

 

if 문이 아닌 while 문을 이용 했다는 것은 참일 동안 계속 이용하겠다는거겠지?

하지만  while 문에서는 조건식에 대한 변경이 없다.

그럼 무한 루프 일텐데 왜 잘되는 걸까?

 

 

 

 

 

 

i가 2 일때,

 

 

 

temper[1]

이랑

temper[2] 을 비교한다.

 

74< 75 true

 

 

 

 

 

 현재 스택 top 값은 1

1을 pop 했으니까 1이 제거가 된다.

 

index에 1이 들어가고

result [1] 에는 2 - 1 =1

이 저장

 

 

 

 

 

 

아 stack 을 pop 했기 떄문에 조건문이 계속 달라지는구나

 

그러면

temper[0] 이랑 temper[2] 을 비교한다.

73 < 75 true

 

stack 에 있는 0을 index에 넣고 

 

result[0] 번에 2 - 0 = 0

를 넣어준다.

 

 

 

 

 

 

 

 

그러면 스택은 비워지니까 while문을 빠져 나간다.

 

stack에는 2민 쌓이게 되는데

 

 

 

 

 

 

 

 

 

 

 

i가 3이 되었을 때

 

temper[2] 이랑 temper[3] 을 비교한다.

75 < 71 false

 

 

거짓이다.

 

 

 

 

 

 

 

stack 에는 현재 2와 3이 쌓여 있다

 

 

 

 

 

 

 

 

 

 

 

i가 4가 되었을 때

 stack top 은 3

 

temper[3] 이랑 temper[4] 을 비교한다.

71 < 69 false

 

 

 

 

 

 

 

 stack 에는 2, 3, 4 가 쌓여 있다

 

 

 

 

 

 

 

 

 

 

 

즉, 나보다 온도가 높은 날을 만나야 while 문을 실행 하는구나

 

i 가 5 일떼

 stack top 은 4

 

temper[4] 이랑 temper[5] 을 비교한다.

69 < 72 true

 

 

 

 

 

 

 

 top 은 4

pop 했으니까 이제 stack 2, 3

 

 

 

 

 

 

 

 

 

 

  resulu[4] = 5 - 4 = 1

 

 

 

 

 

 

 

 

 

 

stack top = 3

 

temper[3] 이랑 temper[5] 을 비교한다.

71 < 72 true

 

 

 

 

 

 

  

3을 pop

 

 

 

 

 

 

 

 

 

 

 

 

 

result[3] = 5 - 3 = 2

 

 

 

 

 

 

 

 

 

 

stack 의 활용성을 이렇게 써보는구나, 역시 이해가 안될 때는 하나씩 짚어보는게 답이구나. 시작할 때 보다는 이해가 가지만 완벽한 이해는 아니다. 내일 또 봐야지