[LeetCode#739] Daily Temperatures

❒ Description

---

제목	Daily Temperature
링크	https://leetcode.com/problems/daily-temperatures/description/
자료구조	스택
시간 복잡도	O(n)

 

이번 문제의 핵심은 인덱스이다. 

그리고 두 가지 풀이가 있는데 첫 번째는 Stack + Index 이고, 두 번째는 Index만을 사용하는 문제풀이다.

비교 이미지

 둘 해결책 모두 O(n)의 시간 복잡도를 가진다. 하지만 두번 째 솔루션이 6ms로 4배정도 빨랐다.

 

 

 

 

 

 

❒ Solution

---

1. Stack

아래 코드는 최초에 작성한 코드로 runtime 26ms를 기록한 코드이다.

 

public int[] dailyTemperatures(int[] temperatures) {
	int[] result = new int[temperatures];
	Queue<Integer> statck = new ArrayDeque<>();
   
	for (int i = 0; i < temperatures.length(); i++) {
		while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
			int last = stack.pop();
			result[last] = i - last;
		}
		stack.push(i);
	}
	return result;
}

 

 

2. Only Index

아래 코드는 leet-code solution에서 가장 빠른 runtime 6ms를 기록한 코드이다.

public int[] dailyTemperaturesV2(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    int hottest = 0;
    for (int i = n-1; i >= 0; i--) {
        int cur = temperatures[i];
        if (cur >= hottest) {
            hottest = cur;
            continue;
        }

        int count = 1;
        while (cur >= temperatures[i + count]) {
            count += result[i + count];
        }
        result[i] = count;
    }
    return result;
}

코드 분석

• for문을 역순으로 순회하고 있다.
• 이전 결과 값 result[x]를 재사용한다.

Input이 `[9, 7, 5, 2, 10]`인 경우를 살펴봤다.

i	hottest	cur	while문 순회	result
4	10	10	0	[ 0, 0, 0, 0, 0 ]
3	10	2	0	[ 0, 0, 0, 1, 0 ]
2	10	5	1	[ 0, 0, 2, 1, 0 ]
1	10	7	1	[ 0, 3, 2, 1, 0 ]
0	10	9	1	[ 4, 3, 2, 1, 0 ]

 

결과적으로 `temperatures[i]`는 `temperatures[i+1]`이 hottest 까지 몇 칸을 갔는지 확인하고 그

값에 1 만 더 한 것이다. 만약 바로 다음 값이 변곡점이라면 while 문을 순회하지 않고, count 값을 `result[i]`에

저장한다. 

 

 

 

 

 

❒ 왜 4배의 차이가 생길까?

---

1. Stack Operation

solution2는 stack 연산이 없다. 물론 push와 pop 연산이 O(1)의 시간 복잡도를 갖지만, 

여러번의 연산 과정이 있기 때문에 runtime에 차이가 발생한다.

 

2. Optimized while loop & Caching

solution2의 경우에는 solution1에 비해 while 조건문이 단순하다. 그리고 데이터를 재사용하는 빈도가 높아

Cache-Hit rate가 높다. 이 점이 실제 runtime 성능을 크게 향상시킨 것 같다.

 

  

 

 

 

 

 

---