주식가격 (42584) - 프로그래머스 [코테][알고리즘]
프로그래머스 programers 주식가격 (42584)문제의 풀이와 해설을 합니다.
[프로그래머스] 코딩테스트 연습 > 스택/큐 > 주식가격 (42584)
이중 for 문을 사용한 풀이법 뿐이라 stack을 사용한 방법으로 해결, 시간 복잡도가 훨씬 줄어드는 방법.
문제 조건
1, 2, 3, 2, 3 의 주식 값 배열이 주어 졌을 경우, 주식 값이 떨어지지 않는 날을 각각 배열에 담아 반환
1, 2, 3, 2, 3 <= 주식 값
4, 3, 1, 1, 0 <= 주식 값이 떨어지지 않는 날
1 => 떨이지는 날이 없으므로 2, 3, 2, 3 => 총 4일간 유지
2 => 역시 떨어지는 날이 없으므로 3, 2, 3 =>총 3일간 유지
3 => 다음 날이 2 이므로 주식 값이 떨어지므로 => 총 1일간 유지 (이부분이 헷갈릴 수 있음)
2,3 => 1일이고
2,1 => 1일 임
2,3,4 => 2일 이고
2,2,1 => 2일 임
즉 다음 날이 주식 값이 떨어지는 날도 1일로 포함 하는 조건 인데(헷갈리는 요소)
2 => 다음 날이 3이고 더이상 없으므로 => 총 1일간 유지
3 => 다음 날이 없으므로 => 0일간 유지
Stack을 이용한 방법
1, 2, 3, 2, 3 뒤에서 부터 루프를 시작한다 => 3, 2, 3, 2, 1 => 마지막은 항상 0일 이므로 뒤에서 마지막을 제외하고 시작
즉 2, 3, 2, 1 를 루프 돌린다.
- Stack에는 두 값을 저장한다 => 주식값, 떨어지지 않는 날 수.
- Stack이 비어 있지 않고, Stack의 마지막 값 >= 현재 주식값 인경우 => 꺼낸다.
- 꺼낸 값에서 주식이 떨이지지 않는 날을 합산한다.
- Stack에 주식값, Stack 에서 합산된 주식이 떨어지지 않는 날 + 1 => 저장한다.
단계별 데이터 상황 설명
2, 3, 2, 1
주식값 = 2 , stack = empty, 주식 유지 날 = 0+1
=> stack 저장 값 = (2, 1) (조건에 의해 stack pop 하지 않음)
주식값 = 3 , stack = (2,1), 주식 유지 날 = 0+1
=> stack 저장 값 = (3,2)(2, 1) (조건에 의해 stack pop 하지 않음)
주식값 = 2, stack = (3,1)(2,1), 주식 유지 날 = (1+1)+1
=> stack 저장값 = (3,3) (조건에 의해 stack에 값을 pop 하여 주식 유지 날을 합산 하고 +1 하여 저장함)
주식값 = 1, stack = (3,3), 주식 유지 날 = (3) + 1
=> stack에 저장 값 (1,4) 조건에 의해 stack에 값을 pop 하여 주식 유지 날을 합산 하고 +1 하여 저장함)
각 개별 주식 가격 유지 날 수 는
1, 2, 3, 2, 3 <= 주식 값
4, 3, 1, 1, 0 <= 주식 값이 떨어지지 않는 날
소스코드
public static int[] solution(int[] prices) {
Stack<Integer[]> stack = new Stack<>();
int[] ret = new int[prices.length];
for (int i = prices.length - 2; i >= 0; i--) {
int day = 0;
while (!stack.isEmpty() && stack.peek()[0] >= prices[i]) {
day += stack.pop()[1];
}
ret[i] = stack.push(new Integer[]{prices[i], day + 1})[1];
}
return ret;
}
