반응형
문제 URL
https://school.programmers.co.kr/learn/courses/30/lessons/42584
나의 코드 (O(N²) 알고리즘)
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
for(int i = 0; i < prices.length; i++){
int num1 = prices[i];
int cnt = 0;
for(int j = i + 1; j < prices.length; j++){
cnt++;
if(num1 > prices[j]) {
break;
}
}
answer[i] = cnt;
}
return answer;
}
}
설명
- 이중 for 문을 사용하여 현재 시점의 가격과 이후의 가격들을 하나씩 비교합니다.
- 주식 가격이 떨어지는 순간을 찾으면 break하여 루프를 종료하고, 떨어지지 않으면 cnt를 증가시킵니다.
- 최종적으로 각 시점마다 계산된 cnt를 answer 배열에 저장합니다.
시간 복잡도
- O(N²)
- 각 요소에 대해 나머지 요소들과 비교하기 때문에 이중 루프가 발생합니다.
- 입력 데이터가 커질수록 성능 저하가 발생할 수 있습니다.
개선된 코드 (O(N) 알고리즘)
import java.util.Stack;
class Solution {
public int[] solution(int[] prices) {
int n = prices.length;
int[] answer = new int[n];
Stack<Integer> stack = new Stack<>();
stack.push(0);
for (int i = 1; i < n; i++) {
// 스택에 있는 값이 현재 값보다 크면 해당 주식 가격이 떨어진 시점을 계산
while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
int index = stack.pop();
answer[index] = i - index;
}
// 스택에 현재 인덱스 추가
stack.push(i);
}
// 아직 스택에 남아있는 값은 끝까지 가격이 떨어지지 않은 경우
while (!stack.isEmpty()) {
int index = stack.pop();
answer[index] = n - index - 1;
}
return answer;
}
}
설명
- 스택 사용
- 스택에는 가격이 떨어질 가능성이 있는 인덱스만 저장됩니다.
- 현재 가격이 스택의 최상단 인덱스에 해당하는 가격보다 낮다면, 해당 인덱스의 결과를 계산하고 스택에서 제거합니다.
- 시간 복잡도
- O(N)
- 각 인덱스가 스택에 한 번 추가되고 한 번 제거되므로, 총 연산 횟수는 배열 길이에 비례합니다.
- O(N)
예제로 이해하기
prices = [1, 2, 3, 2, 3]
- 초기 스택은 비어 있음: stack = []
- i = 0, prices[0] = 1
- 스택이 비어 있으므로 0을 추가: stack = [0]
- i = 1, prices[1] = 2
- prices[stack.peek()] = 1 < 2: 가격이 하락하지 않았으므로 1을 추가: stack = [0, 1]
- i = 2, prices[2] = 3
- prices[stack.peek()] = 2 < 3: 가격이 하락하지 않았으므로 2를 추가: stack = [0, 1, 2]
- i = 3, prices[3] = 2
- prices[stack.peek()] = 3 > 2: 가격이 하락했으므로 2를 스택에서 제거하고 계산.
- answer[2] = 3 - 2 = 1
- 다시 비교: prices[stack.peek()] = 2 == 2: 추가로 처리할 필요 없음.
- 3을 추가: stack = [0, 1, 3]
- prices[stack.peek()] = 3 > 2: 가격이 하락했으므로 2를 스택에서 제거하고 계산.
- i = 4, prices[4] = 3
- prices[stack.peek()] = 2 < 3: 가격이 하락하지 않았으므로 4를 추가: stack = [0, 1, 3, 4]
- 마무리
- 스택에 남아 있는 인덱스는 끝까지 가격이 떨어지지 않았던 경우입니다. 이를 계산:
- answer[0] = 4 - 0 = 4
- answer[1] = 4 - 1 = 3
- answer[3] = 4 - 3 = 1
- answer[4] = 0
- 스택에 남아 있는 인덱스는 끝까지 가격이 떨어지지 않았던 경우입니다. 이를 계산:
- i = 0, prices[0] = 1
결론
스택에는 아직 가격이 하락한 시점이 나오지 않은 인덱스들만 저장되며, 이후 값들을 비교하며 하락 여부를 계산합니다. 이렇게 하면 불필요한 비교를 줄이고 효율적으로 결과를 도출할 수 있습니다.
반응형
'알고리즘 > Java' 카테고리의 다른 글
[프로그래머스] 표 편집 - 81303 (Java) (0) | 2024.12.13 |
---|---|
[프로그래머스] 크레인 인형 뽑기 게임 - 64061 (Java) (0) | 2024.11.29 |
[프로그래머스] 괄호 회전하기 - 76502(Java) (0) | 2024.11.26 |
[프로그래머스] 짝지어 제거하기 - 12973 (Java) (0) | 2024.11.26 |
[프로그래머스] 실패율 - 42889 (Java) (0) | 2024.10.29 |