알고리즘 문제 풀이를 블로그에 올리는 이유는 풀이, 코드를 기록하기 위함이니
앞으로 문제를 다 긁어오기보다 링크만 두고 풀이가 잘 보이도록 포스팅 할 예정입니다!

📄 문제

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

---

👩‍💻 풀이

1. 문제 이해

이 문제는 문제설명을 이해하는 것부터 문제(?)였다.💨
이 문제는 초 별로 주식 가격이 담긴 배열을 주고, 가격이 떨어지지 않는 시간을 각각 구해서 반환하는 문제이다.

입출력 예로 제시된 [1,2,3,2,3]을 보자

1 : 2, 3, 2, 3	=> 끝까지 가격이 떨어지지 않았음		=> 총 4초동안 가격 하락X 
2 : 3, 2, 3	=> 마찬가지로 끝까지 가격이 떨어지지 않았음 	=> 총 3초동안 가격 하락X
3 : 2, 3	=> 1초 후 가격이 2로 떨어졌음		=> 총 1초동안 가격 하락X
2 : 3		=> 끝까지 가격이 떨어지지 않았음		=> 총 1초동안 가격 하락X
3 : 		=> 마지막 값이라 측정X			=> 마지막 값이라 0초동안 하락X

때문에 return 값은 [4,3,1,1,0]이 된다.

2. 이중 for문 활용 풀이

사실 이 문제는

• 이중 for문으로 prices 값을 하나씩 비교하면서,
• 전에 있는 값이 뒤에 있는 값보다 작거나 같을 때는, return 할 배열의 해당 인덱스 값을 하나씩 올려주고,
• 전에 있는 값이 뒤에 있는 값보다 커지면, 반복문을 벗어나 다음 값이 비교되도록 하면 쉽게 풀 수 있다.
  (정말 문제를 이해하는게 문제였고 코드 쓰는건 덜 어려웠다..)

public class Q1_1 {
    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++) {
                if (prices[i] > prices[j])
                    break;
                answer[i]++;
            }
        }
        return answer;
    }
}

3. 스택 활용 풀이

위의 풀이는 문제만 보고 생각했을 때, 차례로 값을 비교해주어야한다는 점에서 직관적으로 생각해낸 풀이였다.
그런데 이 문제의 분류가 스택/큐로 되어있었기 때문에 해당 방법을 사용한 풀이를 고심해보고 시도해보았지만...그닥 성공적이지 못해서ㅜ
프로그래머스 다른 사람의 풀이, 구글링을 참고하여 풀이를 찾아보고 코드를 이해하려 노력했다.
(생각보다 스택을 활용한 풀이가 많지도 않았다ㅜ)

• return 할 배열 answer와 주식가격 변화를 시간과 함께 체크할 stack 생성
• 반복문 1) prices.length만큼 도는 for문으로 prices의 값 하나하나 체크
  - 반복문 1-1) 반복문 실행 중 스택이 비어있지 않고, 주식가격이 떨어졌을 때 answer에 값을 넣어주고 해당 인덱스는 stack에서 pop하는 로직 구현
  - 그 외의 경우(스택이 비어있거나(=처음), 주식가격이 떨어지지 않았을 경우에는 해당 인덱스를 stack에 push
• 반복문 2) 끝까지 stack에서 pop되지 않은 수가 있다. = 끝까지 가격이 떨어지지 않은 주식이 있다.
  전체 길이에서 해당 인덱스를 빼주고, stack에서 pop하여 마무리

public class Solution {

    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                answer[stack.peek()] = i - stack.peek();
                stack.pop();  // 답을 구했기 때문에 stack에서 제거
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }

        return answer;
    }
}

처음에 코드를 보고 순차적으로 이해하고 넘어가려고하다보니,
push를 한 적이 없는데 왜 pop을 하지???하고 멍청미궁에 빠져버렸는데
모르겠는 부분은 일단 넘어가자하고 보니
while문으로 주식가격이 떨어졌을 때 이전 answer들에 시간 값을 넣어주는 부분을 구현하고
아래에 그 외의 경우 다 push하도록 구현하신 것을 발견했다.

아래 출처에서 자세히 적어주신 풀이를 보고 어렵게 이해하긴했지만,
문제를 보고 바로 스택을 떠올리기가 어려울 것 같지만
stack을 이런 식으로 사용하는 것이구나를 배울 수 있었다.

풀이 및 코드 출처 : [프로그래머스] 주식가격(Stack) - JAVA