[프로그래머스] 주식가격

코드 힌트

2중 for문으로 풀기

이 방법은 가격이 떨어지는 시점을 찾기 위해 두 번 반복문을 사용하는 방법입니다.

1. 초기화:
   • 결과를 저장할 배열 result를 prices 배열의 크기만큼 초기화합니다.
   • 모든 요소가 0으로 설정됩니다.
2. 이중 루프:
   • 첫 번째 루프는 각 가격을 순차적으로 확인합니다.
   • 두 번째 루프는 현재 가격 이후의 가격을 비교합니다.
3. 가격 하락 확인:
   • 만약 가격이 떨어지는 순간을 찾으면, 그 시점까지의 시간을 result 배열에 기록합니다.
4. 가격 유지 처리:
   • 끝까지 가격이 떨어지지 않는 경우에는 남은 시간을 result 배열에 기록합니다.

---

Stack을 활용하여 풀기

이 방법은 스택을 사용하여 가격이 떨어지는 시점을 효율적으로 찾는 방법입니다.

1. 초기화:
   • 결과 배열 result와 인덱스를 저장할 스택을 초기화합니다.
2. 가격 비교 루프:
   • 가격 배열을 순차적으로 탐색하면서 스택에 인덱스를 저장합니다.
   • 현재 가격이 스택에 저장된 인덱스의 가격보다 낮으면, 스택에서 인덱스를 꺼내서 하락 시점을 result 배열에 기록합니다.
3. 가격 하락 처리:
   • 스택이 비어있지 않고, 스택의 맨 위 인덱스의 가격이 현재 가격보다 클 때, 스택에서 인덱스를 꺼내서 하락 시점을 기록합니다.
4. 가격 유지 처리:
   • 루프가 끝난 후에도 스택에 남아있는 인덱스는 끝까지 가격이 떨어지지 않은 경우로, 남은 시간을 result 배열에 기록합니다.

 

 

 

---

정답은 더보기 클릭

1. 2중 for문

class Solution {
    public int[] solution(int[] prices) {
        // prices 배열 크기만큼 초기화(모든 요소가 0으로 설정됨)
        int[] result = new int[prices.length];
        
        // 0~n-1까지 요소를 확인하기
        for (int i = 0; i < prices.length - 1; i++) {
            // i에 있는 price를 i+1~n-1까지 확인하기
            for (int j = i + 1; j < prices.length; j++) {
                // i번째가 j번째보다 크다면(값이 떨어졌다면)
                if (prices[i] > prices[j]) {
                    // 몇 초 뒤에 떨어지는 지 값 넣기
                    result[i] = j - i;
                    break;
                }
            }
            // result[i]가 0일 때 (끝까지 배열을 돌았을 때 떨어지는 가격이 없을 때)
            if (result[i] == 0) {
                result[i] = prices.length - 1 - i;
            }
        }
        
        return result;
    }
}

 

2. stack으로 풀기

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        // 결과 배열 초기화 (모든 요소가 0으로 설정됨)
        int[] result = new int[prices.length];
        // 가격 인덱스를 담을 스택 초기화
        Stack<Integer> stack = new Stack<>();
        
        // 가격 배열을 순회
        for (int i = 0; i < prices.length; i++) {
            // 스택이 비어있지 않고, 스택의 맨 위 인덱스의 가격이 현재 가격보다 클 때
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int index = stack.pop();
                // 가격이 떨어진 시점까지의 시간을 계산하여 결과 배열에 저장
                result[index] = i - index;
            }
            // 현재 인덱스를 스택에 추가
            stack.push(i);
        }
        
        // 스택에 남아있는 인덱스 처리 (끝까지 가격이 떨어지지 않은 경우)
        while (!stack.isEmpty()) {
            int index = stack.pop();
            // 배열의 끝까지 가격이 유지된 시간 저장
            result[index] = prices.length - 1 - index;
        }
        
        return result;
    }
}