양수로 이루어진 온도 배열 T가 주어졌을 때, 각 날짜를 기준으로 다음으로 더 따뜻한 날이 올 때까지 며칠이 걸리는지 계산하는 것이 이번 문제의 목표입니다.
문제 예시
입력: T = [73, 74, 75, 71, 69, 72, 76, 73]
출력: [1, 1, 4, 2, 1, 1, 0, 0]
설명: 주어진 온도 목록 [73, 74, 75, 71, 69, 72, 76, 73]에서 첫 번째 날(73도)은 바로 다음 날인 Day 1에 74도로 더 따뜻해지므로 결과값은 1입니다. 같은 방식으로 모든 날짜를 계산하면, 여섯 번째 날의 76도가 전체 기간 중 가장 따뜻한 온도이기 때문에 그 이후에는 더 따뜻한 날이 존재하지 않아 마지막 두 값은 0이 됩니다. 따라서 최종 출력은 [1, 1, 4, 2, 1, 1, 0, 0]입니다.
문제 해결 접근 방법
온도 목록이 주어졌을 때, 각 날짜로부터 다음으로 더 따뜻한 날이 오기까지의 일수를 계산해야 합니다.
이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 처음에 스택은 비어 있으며, 배열을 순차적으로 탐색하면서 현재 온도가 스택 맨 위(top)에 저장된 인덱스의 온도보다 높다면, 해당 인덱스를 팝(pop)하면서 두 인덱스의 차이만큼을 결과에 저장합니다. 그리고 현재 인덱스를 스택에 푸시(push)합니다. 이렇게 하면 스택에는 아직 더 따뜻한 날을 찾지 못한 날짜들의 인덱스만 남게 되며, 단순 이중 반복문(O(n²))보다 훨씬 효율적인 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.
알고리즘 단계
- 온도 데이터를 입력받습니다.
- dailyTemp(int *T, int n) 함수는 온도 배열을 입력받아 각 날짜별로 다음 더 따뜻한 날까지의 일수가 담긴 리스트를 반환합니다.
- 결과를 저장할 벡터 또는 배열을 생성하고 0으로 초기화합니다.
- 온도 배열을 순회하면서, 스택이 비어 있지 않고 현재 온도 T[i]가 스택 top 인덱스의 온도보다 크면 pop하여 일수를 계산합니다.
- 현재 인덱스를 스택에 push합니다.
- 결과를 저장한 후 출력하고 반환합니다.
C++ 코드 예시
#include<bits/stdc++.h>
using namespace std;
void dailyTemp(int *T, int n) {
stack <int> s;
int ans[n];
memset(ans, 0, sizeof(ans));
for (int i = 0; i < n; i++) {
// 스택 top의 온도가 현재 온도보다 낮으면 더 따뜻한 날을 찾은 것
while (!s.empty() && T[s.top()] < T[i]) {
int j = s.top();
s.pop();
ans[j] = i - j;
}
s.push(i);
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
}
int main() {
int n = 8;
int T[8] = {73, 74, 75, 71, 69, 72, 76, 73};
dailyTemp(T, n);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
1 1 4 2 1 1 0 0
출력된 값은 각 날짜별로 더 따뜻한 온도가 며칠 후에 도래하는지를 의미하며, 가장 따뜻한 날인 Day 6(76도) 이후에는 더 따뜻한 날이 없으므로 0이 출력됩니다.