[프로그래머스] 주식 가격 (이중 for문, Stack)

# 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

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

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 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초간 가격이 떨어지지 않았습니다.

# 풀이 (자바)  - 이중 for 문 

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

 

#느낀점

사실 이 문제는 문제 이해가 잘 되지 않아서 지문을 몇 번씩 읽었었다 😂

나와 같은 사람들을 위해 문제에 대해 조금만 더 얘기해보자! 입출력 예시를 '초' 단위 대신 설명을 위해 '일'단위로 바꿔 설명해본다면3, 

 

먼저 총 5일동안의 주식 기간이 있다고 가정해보자! 

[1, 2, 3, 2, 3] 

• 첫 날 주식의 가격은 1달러이다. 둘째 날, 셋째 날, 셋째 날, 다섯째 날의 주식 가격은 각각 2, 3, 2, 3 달러 이므로 1달러에 산 주식은 4일동안 하락하지 않았다! 
• 둘째 날 주식의 가격은 2달러이다. 셋째 날, 넷째 날, 다섯째 날의 주식 가격은 3, 2, 3 달러 이므로 2달러에 산 주식은 3일동안 하락하지 않았다. 
• 셋째 날 주식의 가격은 3달러이다. 넷째 날과 다섯째 날의 주식 가격은 총 2달러 3달러이다. 넷째 날에 2달러로, 3달러에 산 주식의 가격보다 낮아, 주식 가격이 하락했다! 주식을 구매한 다음날 하락했으므로, 주식을 구매하고 떨어지기 전까지의 시간인 하루동안 가격이 하락하지 않았다.
• 넷째 날 주식의 가격은 2달러이다. 다섯째 날 주식의 가격은 3달러이다. 2달러에 산 주식은 1일동안 하락하지 않았다.
• 마지막 날(다섯 째 날)의 주식 가격은 하락할 일이 없다. 즉, 0일동안 하락하지 않게 된다.  

즉, return 값이 [4, 3, 1, 1, 0]이 되게 되는 것이다.

 

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

나는 이중 포문을 이용하여 주식 가격이 하락하기 까지의 일 수를 answer[i]에 담는 식으로 풀었다. 

차례로 값을 비교한다는 점에서 직관적으로 생각했던 풀이 방법이었는데, 이 문제의 카테고리는 사실 스택/큐 이다. (이중 반복문 사용 시 시간 복잡도도 O(N^2)으로 비효율적이기도 하다...)

 

그래서 문제를 풀고 난 뒤, 더 효율적인 방법이 있을 거라고 생각해 stack을 사용하여 풀려고 해봤으나 쉽지 않았었다...

2시간을 고민해보다가 해결이 되지 않아, 구글링을 통해 아래 코드를 찾고 이해해보려했다. 

# 풀이 (자바)  - Stack

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(); // answer 인덱스에 얼마만에 찾았는지 적어준다 
                stack.pop(); // 답을 구했기 때문에 stack에서 제거한다
            }
            stack.push(i);
        }

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

        return answer;
    }

}

코드 출처: https://girawhale.tistory.com/7

 

• return할 배열 answer와 주식가격 변화를 시간과 함께 체크할 stack 생성
• 먼저 prices.length만큼 도는 for문으로 prices의 값 하나하나 체크
  • 반복문을 돌며 prices[stack.peek]과 비교하여 스택이 비어있거나(=처음), 주식이 감소하지 않았다면 stack에 시간 index를 push
  • 만약 감소하는 값이 등장한다면 주식이 감소한 시점이므로 stack에서 해당 인덱스를 제거하고 i(현재 주식의 감소 시점) - stack.peek(주식이 처음 들어간 시점) 값을 answer[stack.peek]값에 넣어준다
• stack에 끝까지 남아 있는 경우는 끝까지 주식 가격이 떨어지지 않는 경우이므로, stack이 비어있을 때까지 prices.length - index - 1를 넣어준다.

코드를 살펴보니, stack이 비어있을 때(처음 시작, i = 0)는 stack,push(0)를 통해 먼저 stack을 생성했다. 
그리고 그 다음 반복문을 돌 때(i = 1), prices[1] < prices[stack.peek()]을 while 문 조건으로 사용했다. stack.peek()에는 0, 즉 이전에 push 했던, 이전 인덱스 값이 들어있다! 
그리고 주식 가격이 떨어졌을 때, 이전 answer에 총 기간을 넣어주게 된다. 

 

한 풀이 방법에 여러가지 풀이 방법이 있을 수 있다는 것은 코딩의 묘미인 것 같다. 

다른 사람들의 더 나은 풀이 방법을 볼 때면, 이런 방법도 있구나! 하면서 무릎을 탁 치게 된다. 

나도 언젠간 다른 사람이 무릎을 탁 치는 코드를 짜고싶다 :)