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

코드

def solution(prices):
    answer = []
    
    prices = list(reversed(prices))
    for index, price in enumerate(prices):
        if len(answer) == 0:
            answer.append(index)
        else:
            flag = False
            for i in range(index-1, -1, -1):
                if prices[i] < price:
                    answer.append(index-i)
                    flag = True
                    break
            if not flag:
                answer.append(index)
    
    answer = list(reversed(answer))
    return answer

 

문제 풀이

 

스택/큐 문제라는데 어떻게 써야할지 감이 안잡혔다. (지금도...)

 

첫번째 시도에선

비교해야 하는 값(prices[index]) 과 나머지 값들(prices[index+1:]) 을 전부 보고

 

나머지 값들중 가작 작은값 (min(prices[index+1:])) 이 비교값보다 클 경우엔 해당 index값을 추가

 

비교값보다 작을 경우 나머지 값들을 반복해서 보면서 비교값보다 작은 값이 나오면 (index-lower_prices_index) 추가

답은 맞췄지만 효율성 테스트에서 통과하지 못했다.

 

 

두번째 방법으로는 위의 과정을 거꾸로 뒤집어서 풀었다.

 

먼저 prices 를 반대로 뒤집는다.

뒤집은 뒤, index 값을 answer 에 추가하는데

추가하기 전 이전 price들과 비교해 작은 값이 존재할 경우 index - prev_index 된 값을 넣어준다.

반환하기전 answer 를 반대로 뒤집어 주면 답이 된다.

 

위 첫번째 방법과 다른점은 비교대상이 상대적으로 적다는거...? (방법 자체는 동일하다보니...)

동일한 점은 스택,큐를 안쓰고 풀었다는 점이 걸린다.

 

문제는 여기

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

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

 

*****추가******

스택, 큐로 어케 푸는지 동기 단톡방에 질문하니 바로 코드가 날라왔다.

import java.util.*;

public class Solution {
	public int[] solution(int[] prices) {
		int[] res = new int[prices.length];
		Stack<int[]> st = new Stack<>();
		
		for(int i=prices.length-2; i>=0; -—i){
			int price = prices[i], day = 1;
			while(!st.isEmpty() && price <= st.peek()[0]) day += st.pop()[1];
			res[i] = st.push(new int[]{price, day})[1];
		}
		
		return res;
	}
}

자바로 와서 이제 이해 하려고 시도 해야 한다.

변수!

res - 결과를 반환하는 리스트 → 0으로 초기화 되기때문에 반복문 동작시 -2 를 해준다니..

st - 스택!

 

로직 정리

prices.length - 2 부터 0 번째 까지 하나씩..?

뒤에서 거꾸로 보는건 내 아이디어와 동일하고... while 문 조건을 보자

스택이 비어있지 않고,

가장 마지막에 삽입된 값과 비교해서 해당 값이 작으면 스택을 빼면서 day값을 더해준다...?

[1,2,3,2,3] 의 경우로 생각해보자

거꾸로 보니까 [3,2,3,2,1], length-2 index 부터 시작

1. [2,3](price, index) → 스택이 비어있으니 삽입 / [ [2,1] ] (res[3] = 1)
2. [3,2] → 스택에 값이 존재하니 확인 3 ≤ 2 ⇒ false, / 스택에 삽입 [ [2,1], [3,1] ] (res[2] = 1)
3. [2,1] → 스택에 값이 존재, 2 ≤ 3 ⇒ true, 스택에 값 제거 후, day += 1 [ [2,1] ]
   1. [2,1] 계속 비교, 2 ≤ 2 ⇒ true, 스택에 값 제거 후, day += 1 [ ]
   2. 스택에 비워졌으니 삽입 / [ [2,3] ] (res[1] = 3)
4. [1,0] → 스택에 값이 존재, 1 ≤ 2 ⇒ true, 스택에 값 제거후, day += 3 / 스택에 삽입 [ [1,4] ] (res[0] = 4)
5. res 값은 [4,3,1,1,0]
6. 나는 코드 보고 기절...