코딩테스트 고득점 kit / 스택&큐 / 주식가격 / JAVA

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

---

풀이방법 1

import java.util.ArrayDeque;
import java.util.Deque;

class Stock {
	
	private int index;
	private int stock;
	
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
	public int getStock() {
		return stock;
	}
	public void setStock(int stock) {
		this.stock = stock;
	}
	
}

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Deque<Stock> stack = new ArrayDeque<Stock>();
		
        for(int i=0; i<prices.length; i++) {
        	
            while(!stack.isEmpty() && stack.peek().getStock() > prices[i]) {
                Stock stock = stack.pop();
                answer[stock.getIndex()] = i - stock.getIndex();
            }
        	
            Stock stock = new Stock();
            stock.setIndex(i);        	
            stock.setStock(prices[i]);
 
            stack.push(stock);
        }
        
        while(!stack.isEmpty()) {
            Stock stock = stack.pop();
            answer[stock.getIndex()] = prices.length-1 - stock.getIndex();
        }
        return answer;
    }
}

풀이 분석

스택과 필드를 이용한 방법입니다.

스택에 배열의 인덱스와 value값이 저장됩니다.

---

풀이방법 2

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
	public static int[] solution(int[] prices) {

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

		for(int i=0; i<prices.length; i++) {
			while(!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
				int pre = stack.pop();
				prices[pre] = i - pre;
			}
			stack.push(i);
			answer[i] = prices.length-1 - i;
		}
		return answer;
    }
}

별도의 필드 필요없이 스택의 peek메소드를 이용하여 prices배열의 인덱스로 사용한 방법입니다.

스택에는 배열의 인덱스가 저장됩니다.

 

추가로 풀이방법1의 코드의 남아있는 스택을 pop하면서 계산하는 while문이 불필요한 것 같아 제거하였습니다.

충분히 for문 하나로도 돌아갈 수 있다는 것을 알았습니다.

for문의 마지막 문장인 answer[i]에 값이 계속 들어간다고 하더라도 결국엔 for문 내부의 while문에서 prices[pre](이전값)의 값을 바꿔주기 때문에 문제가 없습니다.

---

풀이방법 3 - BEST

public class Solution {
    public static int[] solution(int[] prices) {

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

스택없이 순수 배열로만 푼 방법입니다.

이중 포문을 이용하여 인덱스 i와 같은 값을 같는 인덱스 j의 위치를 찾는 방법입니다.

이전값이 다음값 보다 크면 break 아니면 배열의 길이만큼 가서 answer에 저장해줍니다.

 

정렬 방법중 선택정렬 알고리즘과 굉장히 유사하기 때문에 평소에 라이브러리를 안쓰고 직접 정렬을 구현해보신 분들 이라면 많이 응용해서 쓰셨을것 같습니다.

저같은 경우에는 사실 귀찮아서 라이브러리 많이 갖다 쓰는데 이와 같은 코드를 볼때면 스스로 많이 반성하게 되는 코드입니다.

---

수행속도 비교(nanoTime) **동일한 테스트 케이스를 사용한 결과입니다.

	풀이방법 1	풀이방법 2	풀이방법 3
1차 수행 속도	786,600	258,800	1,800
2차 수행 속도	842,500	254,300	1,900
3차 수행 속도	743,200	254,300	1,900
평균	약 790,767	255,800‬	약 1,833

---

히스토리

chucoding/algorithm