[코딩테스트합격자되기-자바편] 문제12. 주식가격

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

출처: 프로그래머스 - 주식가격

 

내용

 

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

 

제약 조건

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

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
15:55	16:36	41분

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

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

시간 복잡도 O(N) 이내에서 해결해야 한다. 모르겠으면 O(N^2) 방식으로라도 푼다.

 

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

 

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초간 가격이 떨어지지 않았습니다.

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

1. 이중 반복문

   solution(prices) {
    for (i = 0) {
        for (j = i + 1) {
            if (prices[j] >= prices[i]) answer++;
        }
    }
    return answer;
   }

 

구현

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                answer[i]++;
                if (prices[i] > prices[j])
                    break;
            }
        }
        return answer;
    }
}

 

복기하기

저자 권장 시간	권장 시간 복잡도
40분	O(N)

 

답안과 나의 풀이를 비교해보세요

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n]; // 가격이 떨어지지 않은 기간을 저장할 배열

        // 스택을 사용해 이전 가격과 현재 가격 비교
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 0; i < n; i++) {
            // 가격이 떨어졌을 때 (이전 가격의 기간 계산)
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }

        // 가격이 떨어지지 않았을 때
        while (!stack.isEmpty()) {
            int j = stack.pop();
            answer[j] = n - 1 - j;
        }
        return answer;
    }
}

• 스택으로 하는 게 더 어려운 것 같다.
• 결국 마지막 인덱스가 아닌 이상 무조건 1초는 확보하는 건가