leetcode 739 - Daily Temperatures

문제

leetcode 739 - Daily Temperatures 풀러가기

문제 풀이

이 문제는 앞 날짜부터 접근하여 온도가 높은 날을 찾으면 시간 초과가 된다.

따라서, 뒷 날짜의 날 수부터 계산한다. 특정 날짜의 온도에 대한 날수는 변함이 없으므로 dynamic programming으로 풀 수 있다.

T = [73, 74, 75, 71, 69, 72, 76, 73] 라고 할 때,

현재 온도가 75도라고 하자. 이때 75도 보다 따뜻해지는 날의 온도는 76도고, 그때까지의 걸리는 날 수는 4일이다.

뒷 날짜의 날수부터 계산하므로 이미 71, 69, 72, 76도에 대해서는 각 온도보다 따뜻해지는 최소 날 수가 저장되어 있을 것이다.

75(2일째)과 바로 뒷 날(3일째)의 온도인 71를 비교한다. 온도가 더 낮다.

온도가 71인 날의 더 따뜻해지기까지 기다리는 날 수는 2이고, 그때의 온도는 72이다.(5일째)

72는 75보다 작으므로, 72에서 따뜻해지기까지 기다리는 날을 찾으면 76도인 6일째다.

그럼 현재 2일째에서 6일째까지 총 4일을 기다렸으므로 4를 계산 값으로 넣는다.

문제 코드(C++)

1. 전체 코드

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

   class Solution { public:     vector<int> dailyTemperatures(vector<int>& T) {                  if(T.empty()){             return T;         }                  vector<int> d(T.size(), 0);                  for(int i = T.size()-2 ; i>=0;i--){             if(T[i+1]>T[i]){                 d[i] = 1;             }else{                 for(int j = i+1; ;j=j+d[j]){                     if(T[j] > T[i]){                         d[i] = j-i;                         break;                     }                     if(d[j] == 0){                         d[i] = 0;                         break;                     }                 }             }         }                  return d;     } }; Colored by Color Scripter

   cs

   Runtime: 100 ms, faster than 96.01% of C++ online submissions for Daily Temperatures.

   Memory Usage: 40.3 MB, less than 7.46% of C++ online submissions for Daily Temperatures.

---

아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

---