[프로그래머스] 주식가격(Stack/Queue) - Java

문제 링크

 

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

코딩테스트 연습 - 주식가격

 

 

 

풀이

 

1. 이중반복문

 

이중 for문을 돌면서 모든 case를 비교하여 현재 값보다 낮은 값이 나오는걸 찾는 방법이다.

시간 복잡도가 O(n2)가 되므로 다른 방법으로 해결하고 싶었음.

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

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                ans[i]++;
                if (prices[i] > prices[j]) 
                    break;

            }
        }

        return ans;
    }
}

 

 

2. 큐(Queue) 사용

 

근데 큐를 사용해도 시간복잡도는 똑같은거 같은데..

스택으로 푸신 분들 있으신데 참고해봐야 겠다.

import java.util.*;

class Solution {
    class Stock {
        int price;
        int time;
        int index;
        
        public Stock(int price, int time, int index) {
            this.price = price;
            this.time = time;
            this.index = index;
        }
    }
    
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Queue<Stock> queue = new LinkedList<>();
        
        for(int i =0; i<prices.length; i++) {
            queue.offer(new Stock(prices[i], 0, i));
        }
        
        int index = 0;
        while(!queue.isEmpty()) {
            Stock cur = queue.poll();
            for(int i=cur.index+1; i<prices.length; i++) {
                if(cur.price <= prices[i]) {
                    cur.time += 1;
                } else {
                    cur.time += 1;
                    break;
                }
            }
            answer[index++] = cur.time;
        }
        
        return answer;
    }
}