[프로그래머스] 스택/큐 - 주식가격 문제 풀이

오늘은 프로그래머스에서 스택/큐의 마지막 문제로 주식가격 문제 풀이를 해보겠습니다. 스택/큐의 마지막 문제인만큼 얼마나 어렵고 재미있을지 기대가 됩니다. 그럼 주식가격 문제 풀이 함께 하러 가보겠습니다.

 

 

프로그래머스 - 스택/큐 - 주식가격 문제 풀이

 

 

 

 

♠ 문제 정보

• 문제명: 주식가격
• 문제 난이도: Level 2
• 문제 푼 사람수: 27787명
• 사용 가능 언어: 6개 (Java 사용)

 

 

이번 문제도 JavaScript를 활용할 수 없는 관계로 제 2의 주 언어인 Java를 활용해서 문제를 풀어보겠습니다.

 

 

 

 

♠ 문제 설명

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

 

 

문제 진짜 짧습니다. 이런 문제 정말 신기하고 풀고 싶게 만드는 문제네요. 그럼 짧은 문제 설명이지만 간단히 정리해보겠습니다.

• 초단위 주식 가격 리스트 prices의 각 시각 기준으로 가격이 떨어지지 않은 기간에 대한 리스트를 반환
• Input
  • prices: 초단위로 기록된 주식 가격 리스트
• Output: 각 시각 별 가격이 떨어지지 않은 기간의 리스트

 

 

 

 

♠ 제한사항

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

 

 

제한 사항도 정말 간단합니다. 그럼 제한사항도 정리해보겠습니다.

• 1 ≤ prices의 각 주식 가격 ≤ 10,000
• 2 ≤ prices의 길이 ≤ 100,000

 

 

 

 

♠ 입출력 예

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. 가격이 떨어지지 않은 주식의 시각을 넣을 스택 배열을 만든다.
2. 초단위 주식 가격이 기록된 리스트인 prices를 순회하여 주식 가격을 선택한다.
   2-1. 1에서 만든 배열에 값이 있다면 나중에 들어간 순서대로 확인한다.
      2-1-1. 값이 없다면, 2번에서 선택한 가격을 넣는다.
      2-1-2. 값이 있다면, 2번에서 선택한 가격과 비교하여 대소를 비교한다.
         2-1-2-1. 2-1에서 확인 값이 클 경우, 해당 값을 꺼낸다.
            2-1-2-1-1. 2번에서 선택한 가격의 초까지 지난 시간을 비교하여 해당 시각을 return 배열에 입력한다.
            2-1-2-1-2. 2-1번으로 이동하여 다음 값을 선택한다.
         2-1-2-2. 2-1에서 확인 값이 작을 경우, 2번에서 선택한 가격을 넣는다.
3. 반복하여 모두 확인한 결과, 마지막 시각과 비교하여 return 배열에 입력한다.
4. 작성된 return 배열을 반환한다.

 

 

이렇게 알고리즘을 구현할 수 있습니다. 스택에 주식가격과 해당 시각(Index)를 넣어줌으로써 결과 배열의 어느 위치에 넣을지와 흐른 시간을 확인할 수 있습니다. 그럼 코드를 구현해보겠습니다.

 

 

 

 

♠ 코드 구현

class Solution {
    public int[] solution(int[] prices) {
        int N = prices.length;
        int[] answer = new int[N];
        // 1. 가격이 떨어지지 않은 주식의 시각을 넣을 스택 배열을 만든다.
        int[] stack = new int[N];
        int stack_count = 0;
        
        // 2. 초단위 주식 가격이 기록된 리스트인 prices를 순회하여 주식 가격을 선택한다.
        for(int i = 0; i < N; i++) {
            // 2-1. 1에서 만든 배열에 값이 있다면 나중에 들어간 순서대로 확인한다.
            for(int j = stack_count - 1; j >= 0; j--) {
                // 2-1-2. 값이 있다면, 2번에서 선택한 가격과 비교하여 대소를 비교한다.
                if(prices[stack[j]] > prices[i]) {
                    // 2-1-2-1. 2-1에서 확인 값이 클 경우, 해당 값을 꺼낸다.
                    stack_count--;
                    // 2-1-2-1-1. 2번에서 선택한 가격의 초까지 지난 시간을 비교하여 해당 시각을 return 배열에 입력한다.
                    answer[stack[j]] = i - stack[j];
                } else {
                    // 2-1-2-2. 2-1에서 확인 값이 작을 경우, 2번에서 선택한 가격을 넣는다.
                    break;
                }
            }
            // 2-1-1. 값이 없다면, 2번에서 선택한 가격을 넣는다.
            stack[stack_count++] = i;
        }
        
        // 3. 반복하여 모두 확인한 결과, 마지막 시각과 비교하여 return 배열에 입력한다.
        for(int i = 0; i < stack_count; i++) {
            answer[stack[i]] = N - 1 - stack[i];
        }
        
        // 4. 작성된 return 배열을 반환한다.
        return answer;
    }
}

 

 

이번 코드는 상당히 깁니다. 스택을 정석으로 활용하였다고 생각합니다. 스택에서 값을 pop하고 push해야 스택 자료구조를 활용한 것이 아니라, Last In First Out의 데이터 구조만 지킨다면 그것이 바로 스택이라고 생각합니다. 이번 코드에서는 스택을 최대한 효율성 있게 사용한 코드라고 생각합니다. 하지만 이 부분은 최대 배열 길이를 알고 있어야 가능하므로 참고하시기 바랍니다.

 

 

 

 

♠ 채점 결과

 

 

채점 결과 코드가 상당히 효율적으로 구현되었다고 생각이 듭니다. 역시 정확성 테스트 케이스 10개와 효율성 테스트 케이스 5개를 깔끔하게 통과하여 100점을 받았습니다.

 

 

이 글을 보시는 분들도 재미있게 천천히 주식가격 문제 풀이 해보시기 바랍니다.