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

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

---

풀이

풀이 과정

쉽게 생각할 수 있는 방법은 반복문을 이용해 단순 비교를 할 수 있다

이중 반복문을 이용해 특정 시점과 그 이후의 시점들의 가격을 비교해 가격이 떨어지지 않은 시간을 1초씩 증가시키고, 만약 가격이 떨어지게 된다면 반복문을 종료한다

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

---

다음은 문제의 카테고리인 스택을 이용한 풀이

완전 탐색을 이용해도 정확성 및 효율성 테스트를 모두 통과하지만 문제의 카테고리가 스택/큐 이기도 하고 막상 다른사람들의 코드를 보아도 스택을 이용한 풀이가 많이 없어 나름 풀이해보았다

스택은 인덱스값과 가격을 동시에 확인하기 위해 정수 배열 스택을 이용했다

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

 

정답 배열의 각 인덱스마다 각각의 최대 기간을 먼저 넣어주고 가격이 떨어지는 경우에만 해당 인덱스의 값을 바꿔주기로 한다

정수 배열을 만들어 현재 비교할 값의 인덱스와, 가격을 넣어주고 스택의 값과 비교한다

만약 스택이 비어있지 않고 스택에서 꺼낸 가격이 현재 가격보다 높다면 가격이 떨어진 경우이므로 스택에서 꺼낸 값에 해당하는 정답 인덱스를 바꾸어 주어야한다

현재 비교할 인덱스에서 스택에서 꺼낸 값의 인덱스를 빼주면 가격이 떨어지지 않은 기간을 구할 수 있다

비교가 끝났다면 현재 비교한 값을 스택에 넣어준다

for(int i = 0; i < prices.length; i++){
	answer[i] = answer.length - 1 - i; // 최대기간으로 세팅
	Integer[] arr = {i, prices[i]}; // 인덱스, 가격

	while(!stack.empty() && stack.peek()[1] > prices[i]){ // 가격이 떨어진 경우
		Integer[] price = stack.pop();
		answer[price[0]] = i - price[0];
	}

	stack.push(arr);
}

 

최종 코드

// 반복문을 이용한 풀이

import java.util.*;

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

		for(int i = 0; i < answer.length; i++) {
			for(int j = i + 1; j < answer.length; j++) {
				answer[i]++;

				if(prices[i] > prices[j]) break;
			}
		}

		return answer;
	}
}

 

// 스택을 이용한 풀이

import java.util.*;

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++){
            answer[i] = answer.length - 1 - i; // 최대기간으로 세팅
            Integer[] arr = {i, prices[i]}; // 인덱스, 가격
            
            while(!stack.empty() && stack.peek()[1] > prices[i]){ // 가격이 떨어진 경우
                Integer[] price = stack.pop();
                answer[price[0]] = i - price[0];
            }
            
            stack.push(arr);
        }
        
        return answer;
    }
}

 

성능 비교

반복문을 이용한 풀이

스택을 이용한 풀이

---