문제 설명
초 단위로 기록된 주식 가격이 담긴 배열 prices가 주어질 때, 각 가격이 떨어지지 않은 기간은 몇 초인지를 구하는 함수를 작성하는 문제입니다.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.prices의 길이는 2 이상 100,000 이하입니다.
입출력 예시
- 입력:
[1, 2, 3, 2, 3] - 출력:
[4, 3, 1, 1, 0]
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초 뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
문제 해결 방법
- 각 가격이 떨어지지 않은 기간을 계산합니다.
- 이중 for 루프를 사용하여 가격이 떨어지는 시점을 찾습니다.
- 효율적인 계산을 위해 prices 배열의 각 원소에 대해 떨어지지 않은 기간을 계산하고 결과를 저장합니다.
해결 전략
- 각 주식 가격의 인덱스를 기준으로 이후의 가격들과 비교하여 몇 초 동안 가격이 떨어지지 않았는지 계산합니다.
- 이중 for 루프를 통해 비교를 수행하되, 첫 번째 루프는 현재 시간을 기준으로, 두 번째 루프는 그 이후의 시간을 기준으로 합니다.
코드 구현 (이중 for 루프 사용)
function solution(prices) {
const answer = [];
const n = prices.length;
for (let i = 0; i < n; i++) {
let duration = 0;
for (let j = i + 1; j < n; j++) {
duration++;
if (prices[i] > prices[j]) {
break;
}
}
answer.push(duration);
}
return answer;
}입출력 예시 테스트
console.log(solution([1, 2, 3, 2, 3])); // [4, 3, 1, 1, 0]이 코드는 주어진 예시 입력에 대해 올바른 결과를 출력합니다. 모든 가격에 대해 가격이 떨어지지 않은 기간을 정확히 계산할 수 있습니다.
코드 설명
prices배열의 길이를n에 저장합니다.prices배열을 순회하면서 각 가격이 떨어지지 않은 기간을 계산하여answer배열에 저장합니다.- 현재 가격보다 이후의 가격이 낮아지는 시점까지
duration을 증가시키며 반복합니다. - 이후의 가격이 낮아지면
break로 루프를 종료하고,duration값을answer배열에 추가합니다. - 모든 가격에 대해 반복한 후 최종
answer배열을 반환합니다.
스택을 사용한 문제 해결 방법
이 문제는 스택을 사용하여 더 효율적으로 해결할 수 있습니다. 스택을 사용하면 이중 for 루프를 사용하는 것보다 시간 복잡도를 O(n)으로 줄일 수 있습니다.
해결 전략
- 주식 가격의 인덱스를 스택에 저장하면서, 현재 가격이 이전 가격보다 낮아지면 스택에서 인덱스를 꺼내고 기간을 계산합니다.
- 끝까지 가격이 떨어지지 않은 경우도 스택을 이용하여 처리합니다.
코드 구현 (스택 사용)
function solution(prices) {
const answer = Array(prices.length).fill(0);
const stack = [];
for (let i = 0; i < prices.length; i++) {
while (stack.length && prices[stack[stack.length - 1]] > prices[i]) {
const j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}
while (stack.length) {
const j = stack.pop();
answer[j] = prices.length - 1 - j;
}
return answer;
}
console.log(solution([1, 2, 3, 2, 3])); // [4, 3, 1, 1, 0]비교 및 장점
- 시간 복잡도: 이중 for 루프를 사용한 방법은 O(n^2)의 시간 복잡도를 가지지만, 스택을 사용한 방법은 O(n)의 시간 복잡도를 가집니다. 이는 입력 배열의 크기가 커질수록 성능 차이가 크게 나타납니다.
- 효율성: 스택을 사용하는 방법은 각 요소를 한 번만 처리하므로 더 효율적입니다. 이는 특히
prices배열의 길이가 최대값인 100,000에 가까울 때 중요합니다. - 가독성: 스택을 사용하는 방법은 초기에는 이해하기 어려울 수 있지만, 익숙해지면 더 직관적이고 간결하게 코드를 작성할 수 있습니다.
결론적으로, 스택을 사용한 방법은 더 효율적이며, 특히 큰 입력 데이터에서 성능상의 이점을 제공합니다. 코딩 테스트나 실제 애플리케이션에서 성능이 중요한 경우 스택을 활용한 방법을 추천합니다.
1인개발자가 되겠다