[프로그래머스|JAVA] 주식 가격 | 스택 / 큐 사용 ❌ | 간단 풀이 | 스택 / 큐 방법 포함 ⭕️ | 풀이법 2️⃣가지

[문제 링크]

프로그래머스

[문제]

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

 

---

📍 [코드]

 

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = i + 1; j < n; j++) {
                cnt++;
                if (prices[j] < prices[i]) break; // 떨어지면 멈춤
            }
            answer[i] = cnt;
        }
        return answer;
    }
}

 

💡 접근법

• 이중 for문 사용
• 현재 인덱스보다 다음 인덱스 값이 작으면 떨어진 것
  ➡️ 떨어지기 전까지 카운트 후 break

    ✅ 시간 복잡도가 O(N²)이지만, 이 문제 조건으로는 가능

---

 

📍 [Stack 활용]

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        List<Integer> answer = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        
        for(int i = prices.length - 1; i >= 0; i--) {stack.push(prices[i]);}
        
        while (!stack.isEmpty()) {
            int check = stack.get(stack.size() - 1);
            int cnt = 0;

                for (int i = stack.size() - 2; i >= 0; i--) { // 한 칸씩 내려가며 비교
                    cnt++;
                if (stack.get(i) < check) break;
                }

            answer.add(cnt);
            stack.pop(); 
        }
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

💡 접근법

• 위와 같이 스택 한 칸씩 내려가며 비교하고
  ➡️ 값이 작아지면 멈춤
• 값을 직접 삭제하지 않고,.get()으로 값만 가져와서 비교
• 이후 값을 삭제하고 또 제일 위부터 탐색

---

 

💬 한 문제를 여러 방법으로 푸는 것은

나에게 큰 도움이 되는 것 같다.