[프로그래머스 / Java] 코딩테스트 연습: 주식가격 (스택 / 큐)

난이도: Level 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

---

 

문제 지문이 너무 이상해서 이해가 안됐다.

다른 회원분이 문제 지문을 재해석한 버전(아래 링크)을 보면 본 문제의 지문보다는 이해가 잘 될 것이다.

https://school.programmers.co.kr/questions/20326?question=20326

프로그래머스

 

또한 더욱 명확한 해답은 아래와 같다.

그래서 질문 글들을 찾아보는 도중 어떻게 풀어야 할지 알게 되었다.

이것을 적용시키면 이 문제는 매우 쉽게 풀린다.

출처: https://school.programmers.co.kr/questions/40479

 

사실 이 문제는 O(N^2)으로도 풀린다고 한다.

백준처럼 제한 시간을 알려주지 않아서 그런지 기준이 참 모호하다...

그래서 나도 이중 for문을 사용해서 문제를 풀려고 했으나, 스택/큐를 요구하는 문제이므로 큐를 사용해서 풀었다.

큐에 배열 인덱스들을 모두 담고, 큐에서 하나씩 뽑은 인덱스(index)의 prices 배열 값과 index보다 뒤에 있는 prices 배열 값들을 비교해서, index보다 뒤에 있는 prices 배열 값이 더 작다면 더이상 큐에서 뽑은 index의 answer 배열 값을 증가시키지 않고, 큐에서 index를 새로 뽑아서 이 과정을 반복시켰다.

이 말은 아래 코드를 보면 한번에 이해가 될 것이다.

 

전체 코드

import java.util.*;
 
class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Queue<Integer> queue = new LinkedList<>();
        
        // 배열의 인덱스들을 모두 큐에 추가
        for (int i = 0; i < prices.length; i++) {
            queue.add(i);
        }
        
        // 큐가 비어있을 때까지 반복
        while (!queue.isEmpty()) {
            int index = queue.poll();   // 현재 인덱스를 큐에서 뽑기
            
            // 현재 인덱스 + 1부터 prices 배열의 크기만큼 반복
            for (int i = index + 1; i < prices.length; i++) {
                answer[index]++;    // 현재 인덱스의 answer 값 1 증가
                
                // i번째 prices 값이 현재 인덱스의 prices 값보다 작으면 가격이 떨어진 것
                if (prices[i] < prices[index]) {
                    break;  // 더이상 현재 인덱스의 answer 값을 증가시키지 않음
                }
            }
        }
        
        return answer;
    }
}