[알고리즘] 프로그래머스 주식가격 -스택, 큐-

https://programmers.co.kr/learn/courses/30/lessons/42584?language=java

코딩테스트 연습 - 주식가격 | 프로그래머스

 

처음에 리스트로 풀고 테스트케이스도 다 맞길래 통과겠지 싶었다.

public class Solution {

     public int[] solution(int[] prices) {
        int[] answer = {};
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> resultList = new ArrayList<>();
        for (int price : prices) {
            list.add(price);
        }
        int position = 0;
        while (!list.isEmpty()) {
            int value = list.get(position);
            list.remove(position);
            //남은 리스트에서 비교
            for(int i=0; i<list.size(); i++){
                int relativeValue = list.get(i);
                // 가격이 떨어진 경우
                if(relativeValue < value){
                    resultList.add(i+1);
                    break;
                }
                //마지막까지 가격 안떨어진 경우
                else if(i == list.size()-1){
                    resultList.add(i+1);
                    break;
                }
            }
            //하나남은경우 0을 결과에 추가하고 break
            if(list.size() == 1){
                resultList.add(0);
                break;
            }
        }
        answer = resultList.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

하지만 위의 코드는 테스트케이스는 다 통과했지만 효율성에서 실패했다.

그래서 resultList만 배열로 바꿨으나 효율성 총 5개중 2개만 통과가 되었다.

 

 

 

 

결국 다 배열로 바꿔서 효율성 테스트도 모두 통과했다.

제출한 코드는 다음과 같다.

public class Solution {

     public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        int cursor = 0; // answer index cursor

        int position = 0;
        while (position < prices.length) {
            int value = prices[position++];
            //남은 리스트에서 비교
            for(int i = position; i<prices.length; i++){
                int relativeValue = prices[i];
                // 가격이 떨어진 경우
                if(relativeValue < value){
                    answer[cursor++] = i-(position-1);
                    break;
                }
                //마지막까지 가격 안떨어진 경우
                else if(i == prices.length-1){
                    answer[cursor++] = i-(position-1);
                    break;
                }
            }
            //하나남은경우 0을 결과에 추가하고 break
            if(position == prices.length){
                answer[cursor] = 0;
                break;
            }
        }
        return answer;
    }

}

 

 

 

효율성에서 문제가 되면 시간복잡도를 먼저 계산해보도록 하자. 위는 for문도 한번밖에 돌지 않기 떄문에 (심지어 중간에 break문도있다.) 공간복잡도가 원인이라 생각했다

그래서 배열로 다 바꿔봤는데 맞아서 다행이다. 

 

 

댓글과 공감은 큰 힘이됩니다. 감사합니다!!