알고리즘 공부 1일 차(주식 가격)

시작

programmers에 등록된 알고리즘 문제 중 주식 가격 문제가 있다.

처음 문제를 봤을 때 이게 무슨 말인지 이해가 안 되었지만 한참을 고민한 끝에 문제를 이해하게 되었다.

문제 인식

내가 이해한 내용은 다음과 같다.

1. 5초 시점에 가격이 마지막으로 입력된다.
2. 1초 시점에는 1원, 2초 시점에는 2원, 3초 시점에는 3원이라는 것이다.
3. 1초 시점에 1원에 주식을 샀으므로 4초 뒤인 5초 시점에도 가격은 1원 아래로 떨어지지 않았다.
4. 2초 시점에 2원에 주식을 샀으므로 3초 뒤인 5초 시점에도 가격은 2원 아래로 떨어지지 않았다.
5. 3초 시점에 3원에 주식을 샀지만 1초 뒤인 4초 시점에 가격이 3원 아래로 떨어졌다.
6. 4초 시점에 2원에 주식을 샀으므로 1초 뒤인 5초 시점에도 가격은 2원 아래로 떨어지지 않았다.
7. 5초 시점에 3원에 주식을 샀지만, 그 이후 입력된 값이 없으므로 비교 대상이 없어 시간을 계산할 수 없다.
8. 따라서 return 값은 [4, 3, 1, 1, 0]이 된다.

문제 해결

문제를 이해했으니 문제를 해결을 해야 할 시간이다.
우선 문제를 해결하기 위해 Stack 강의를 들었다.
그리고 구글에 '주식 가격 java'를 검색해 나오는 풀이들을 보고 그 중 Stack을 사용하는 코드를 찾았고 해독을 시작했다.
아래 코드는 내가 찾은 코드이다.

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> beginIdxs = new Stack<>();
        int i=0;
        int[] terms = new int[prices.length];

        beginIdxs.push(i);
        for (i=1; i<prices.length; i++) {
            while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]) {
                int beginIdx = beginIdxs.pop();
                terms[beginIdx] = i - beginIdx;
            }
            beginIdxs.push(i);
        }
        while (!beginIdxs.empty()) {
            int beginIdx = beginIdxs.pop();
            terms[beginIdx] = i - beginIdx - 1;
        }

        return terms;
    }
}

코드 해석

그리고 내가 해석한 내용이다.

 for (i=1; i<prices.length; i++) {
 	while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]){
    	int beginIdx = beginIdxs.pop();
    	terms[beginIdx] = i - beginIdx;
   }
   beginIdxs.push(i);
}

prices의 배열의 크기동안 시도를 한다.(for)
stack이 비어있지 않고, 비교대상stack 인덱스의 price값이 현재 비교중인 인덱스의 price값보다 작다면(while)
stack에서 해당값은 빼주고(pop)
term 인덱스에 얼마만에 찾았는지 넣어준다. (term)
그렇게 찾은 값을 stack에 넣는다.(push)

 while (!beginIdxs.empty()) {
 	int beginIdx = beginIdxs.pop();
	terms[beginIdx] = i - beginIdx - 1;
 }

stack이 비어있지 않을 때
stack에서 해당값은 빼주고
term 인덱스에 찾는데 걸린 시간을 넣어준다.

return terms;

마지막으로 term 인덱스를 반환한다.

소감

처음 문제를 보았을 때 return 값이 왜 저렇게 나왔는지 이해가 안 돼서 이해하는 데 시간을 소모를 많이 했다.
그리고 Stack 강의를 들을 때에는 쉽고 이해도 잘되었지만, 막상 이를 적용하려고 하니 해결이 안 되었고 검색 후 코드를 보고 난 후에야 이해가 되었다.
아직 처음이라 이해도가 떨어지는 것 같다.