programmers : stack queue 4(주식가격)[java]

 

https://programmers.co.kr/learn/courses/30/lessons/42584?language=java 

코딩테스트 연습 - 주식가격

 

-문제 설명

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

 

입출력 예

pricesreturn

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

-sol. 1

stack collection class 을 사용하는것 보다 짜기쉽고 코드를 읽고 이해하기도 쉬운것같은 최초 풀이이다.

하지만 카테고리가 stack으로 구분되어있어 찝찝했다.

이중 loop의 첫번째 loop은 비교할 기준 index, 두번째 loop은 기준 인덱스와 비교할 i+1 index 이다

마지막 인덱스를 제외하고 자기 자신이 1초를 유지한것이므로 answer[i]를 무조건 +1하고

값이 떨어지는 시점에 break한다

public class stack_queue_4 {

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

-sol. 2

다른사람이 stack 을 활용한 풀이를 이해가 가지않다 주석을 달아가며 힘들게 이해했다.

stack에 아직 가격이 떨어지지 않는 인덱스들을 저장하는 방식이다.

개인적으로는 위의 풀이와 시간복잡도가 차이가 나지 않는것으로 보이는데 이런경우는 굳이 제시하는 자료구조를 쓰지 않는것이 나을 수 있다고 생각됐다.

public class stack_queue_4 {
    public int[] solution(int[] prices) {
            int[] answer = new int[prices.length];
            Stack<Integer> stack = new Stack<>();
            int i =0;
            stack.push(i); //시작하는 index를 push하고 시작한다

            for(i =1; i < prices.length; i++) {
                while(!stack.empty() && prices[i] < prices[stack.peek()]) { //가격이 떨어지면
                    int start_index = stack.pop(); 
                    answer[start_index] = i - start_index;
                }
                stack.push(i); //다음 인덱스의 가격이 안떨어지면
            }

            while(!stack.empty()) { //끝까지 가격이 떨어지지않은 index 처리
                int start_index = stack.pop();
                answer[start_index] = i -start_index-1; //전체길이 - 현재인덱스 위치(실제길이 위해 -1)해주어 구함
            }
            return answer;
	}
}