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

1.  문제 설명

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

2. 제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

3. 입출력예

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

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

4. 풀이

Solution 1

- 선택정렬을 활용하여 기준이 되는 가격(now)과 떨어질 때의 시점(혹은 마지막)까지의 순회 횟수(low)를 구하여 answer에 넣어준다.

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

        int low=0;
        for(int i=0; i<prices.length; i++){
            int now = prices[i];
            low = 0;
            for(int j=i+1; j<prices.length; j++){
                low++;
                if(prices[j] < now) break;
            }
            answer[i] = low;
        }
        return answer;
    }
}

Solution 2

- 순회 횟수(low)를 구하지 않고 바로 answer[i]를 증가 시켜주는 방법으로 코드를 줄일 수도 있었다.

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

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

Solution 3

- 이 문제가 Stack/Queue 문제여서 해당 방법으로 푸는 방법을 찾아보았다.

import java.util.Stack;
class Solution {
    public int[] solution(int[] prices) {
        int leng = prices.length;
        int[] answer = new int[leng];

        Stack<Integer> s = new Stack<>();
        
        s.push(0);
        for(int i=1; i<leng; i++){
            while(!s.empty() && prices[s.peek()] > prices[i]){
                int idx = s.pop();
                answer[idx] = i-idx;
            }
            s.push(i);
        }
        
        while(!s.empty()){
            int idx = s.pop(); 
            answer[idx] = leng - idx - 1;
        }
        return answer;
    }
}

5. 풀이 설명

결과적으로는 선택정렬로 변수로 따로 주식이 떨어지는 시점을 구하는게 제일 빨랐다.

Stack/Queue로 문제를 고민해 보는것이 이 문제의 의도였던 것 같고, 확실히 새로운 사고방식으로 생각 할 수 있는 풀이였다.

6. 결과 

Solution 1

Solution 2

Solution 3

7. 마치며

친척언니네 집들이를 다녀왔다.

민들레화로에서 특수부위 고기 먹고

친척오빠가 사온 브레드&버터 카베르네 소비뇽 레드와인과 프랑스 치즈를 먹고

섞어 마신 휴유증으로 머리가 깨질듯이 아팠지만 최미삼 순댓국을 포기할 수 없었다.

그리고 바오밥&베이커리 카페에 가서 호주 바오밥나무를 봤다. 거기 크루와상 존마탱이었다.

돌이켜보니 사진이 한장도 없었다. 난 맛집&여행 포스팅은 불가능한걸까.. 

이렇게 글자로라도 남겨본다. ㅋㅋㅋ 

아무튼 집들이 다녀와서 오늘도 이렇게 한문제 풀었다. 예~