.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Plain Text
복사
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Plain Text
복사
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Plain Text
복사
Constraints:
•
1 <= temperatures.length <=
•
30 <= temperatures[i] <= 100
My solution
the number of days you have to wait after the ith day to get a warmer temperature.
너가 기다려야 할 날들의 수의 배열을 구해라. (더 따뜻한 온도를 얻기 위해서 기다려야 하는 날)
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
73을 기준으로 하루만 기다리면 더 큰 값(온도)이 있다.
74를 기준으로 하루만 기다리며 더 큰 값이 있다.
75을 기준으로 4일만 기다리면 더 큰 값이 있다.
71을 기준으로 2일만 기다리면 더 큰 값이 있다.
69를 기준으로 하루만 기다리면 더 큰값이 있다.
72를 기준으로 하루만 기다리면 더 큰 값이 있다.
76를 기준으로 기다려도 더 큰 값이 없다.
73을 기준으로 기다려도 더 큰 값이 없다.
⇒ [1, 1, 4, 2, 1, 1, 0, 0]
for문에서 하나의 기준값을 들고 다음 요소부터 기준값을 빼본다. 그 값이 양수라면 해당 온도는 기준값보다 큰 것이므로 해당 인덱스 - 기준값의 인덱스(기준값을 가지고 있는데 인덱스는 어떻게 기억하지?, 배열 형태로 가지고 다녀야 하나)를 배열에 추가해준다. 양수가 나오지 않으면 계속 이동한다. 만약 끝까지 나오지 않으면 0이다.
제출자의 33%정도보다 빠르게 나왔다. 하지만 stack 문제라고 해서 어떻게 stack으로 풀어야할지 고민해보았다.
const dailyTemperatures = function (temperatures) {
// # : 1. flag와 크기 비교, 이중 for문
const result = [];
for (let i = 0; i < temperatures.length; i++) {
let flag = false;
for (let j = i + 1; j < temperatures.length; j++) {
if (temperatures[j] > temperatures[i]) {
flag = true;
result.push(j - i);
break;
}
}
if (!flag) result.push(0);
}
return result;
JavaScript
복사
콘솔로 찍어보면 2,3,4( 75, 71, 69 ) 인덱스가 stack에 들어간 상태에서 while문 조건에 맞았을 때 하나씩 pop해서 result에 지금 i에 뺀 값으로 들어가는 걸 볼 수 있다.
그래서 stack에 75라는 매우 큰 수가 계속 pop되지 않고 존재하고 있다. 그 상태에서 5번째 인덱스가 들어온다. 이것은 72이다. 그다음이 76이므로 바로 더 큰 걸 만났으므로 빠져나간다.
근데 이때 76은 stack에 들어있던 2(75)보다도 더 큰 값이 따라서 while문이 한번더 반복되면서 stack이 완전히 비어버린다. 그다음은 i가 마지막 인덱스인 6을 가리키고 이는 73이다. for문에 따라 i가 더이상 증가할 수 없어서 while문에 들어갈 수 없는 조건이므로 73은 덩그러니 stack에 남아있다.
이렇게 while문으로 들어가지 못하는 경우에 stack에 끝까지 덩그러니 남는 것들을 result에 담아주어야 할 것이다. 그렇다면 맨 마지막에 stack에 있는 걸 for문으로 돌리면서 그 값을 result 인덱스로 넣어서 result.push(0)해준다.
말로 차근차근 정리해보면 해결방법이 더 잘 떠오르고 집중도 되는 것 같다. 타자를 치면서 손을 움직이는 데에 신경을 쓸 수 밖에 없어서 그런 것 같다.
위에서 stack 없이 33%보다 빨랐는데 stack을 사용하니 가독성이 좋아지고 성능이 대폭 향상되어서 제출자의 52%보다 빠른 런타임을 받을 수 있었다.
다른 사람의 풀이를 보니 애초에 result 배열을 모두 0으로 채워놓는 fill(0) 메서드를 호출한다면 for문을 돌리는 것보다 더 가독성이 좋다고 생각되었다. 이렇게 하면 메모리를 대폭 절약할 수 있다. 단점은 런타임이 조금 더 늘어난다는 점이다.
const dailyTemperatures = function (temperatures) {
const result = new Array(temperatures.length).fill(0);
JavaScript
복사
소스코드
/**
* @param {number[]} temperatures
* @return {number[]}
*/
const dailyTemperatures = function (temperatures) {
// # : 1. flag와 크기 비교, 이중 for문
// const result = [];
// for (let i = 0; i < temperatures.length; i++) {
// let flag = false;
// for (let j = i + 1; j < temperatures.length; j++) {
// if (temperatures[j] > temperatures[i]) {
// flag = true;
// result.push(j - i);
// break;
// }
// }
// if (!flag) result.push(0);
// }
// return result;
// # : stack과 for+while문
const result = [];
const stack = [];
for (let i = 0; i < temperatures.length; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
for (const x of stack) result[x] = 0;
return result;
};
test('TC1', () => {
expect(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])).toStrictEqual([1, 1, 4, 2, 1, 1, 0, 0]);
});
// test('TC2', () => {
// expect(dailyTemperatures([30, 40, 50, 60])).toStrictEqual([1, 1, 1, 0]);
// });
// test('TC3', () => {
// expect(dailyTemperatures([30, 60, 90])).toStrictEqual([1, 1, 0]);
// });
// test('TC4', () => {
// expect(dailyTemperatures([55, 38, 53, 81, 61, 93, 97, 32, 43, 78])).toStrictEqual([3, 1, 1, 2, 1, 1, 0, 1, 1, 0]);
// });
JavaScript
복사
