99클럽 코테 스터디 4일차 TIL - LV3. 주식 가격

 

 

오늘의 학습 키워드

• 스택

오늘의 회고

1. 문제

문제 URL

프로그래머스

 

2. 해결 방안

풀이 1 (for문)

    /**
     * solution1 : 시간 복잡도 안좋음 O(n^2)
     */
    public int[] solution1(int[] prices) {
        int[] answer = new int[prices.length];

        // 배열 돌면서 가격 같거나 늘면 +1 해서 결과에 담기
        for(int i=0; i<prices.length; i++) {
            int cnt = 0;
            for(int j=i+1; j< prices.length; j++) {
                cnt++;
                if(prices[i] > prices[j]) break;
            }
            answer[i] = cnt;
        }
        return answer;
    }

• 이중 포문으로 배열 돌리면서 각 요소보다 작아지기 전까지 카운팅한다.
• 이중 포문이라 시간 복잡도가 안좋다. O(n^2)

풀이 2 (스택)

public int[] solution2(int[] prices) {
    int[] ans = new int[prices.length];
    Stack<Integer> stack = new Stack();

    for (int i = 0; i < prices.length; i++) {
        while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
            ans[stack.peek()] = i - stack.peek();
            stack.pop(); // 답을 구했기 때문에 stack에서 제거
        }
        stack.push(i);
    }

    while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
        ans[stack.peek()] = prices.length - stack.peek() - 1;
        stack.pop();
    }

    return ans;
}

• 현재 요소와 스택의 마지막 요소부터 비교하면서, 스택의 요소가 더 크면(=주식가격 떨어지는 지점) answer[스택index] 에 시간차(i = stack.peek())를 저장한다.
• stack이 계속 쌓인다는 것 = 현재 요소가 이전 요소보다 크다는 것을 의미. 가격이 같거나 증가하고 있는 것이니 떨어지는 지점을 찾는 것이다.
• while 문에서는 stack에서 pop 해도 stack에 요소가 남아있으면 조건에 맞는지 또 검사한다. stack에 남아있는 이전 요소와 현재 요소를 비교하고, 이전 요소(스택에서 peek한 것)가 더 크면 주식 가격이 떨어진 것이므로, 마찬가지로 answer에 기록한다.
• 다 돌았는데 stack 요소가 남아있다면 남은 스택 요소보다 떨어진 지점이 없다는 것. 그 요소는 총 길이 차이를 이용해 시간을 계산해서 answer에 넣어준다.

3. 피드백

• 이중 for문으로는 금방 이해했는데 스택으로는 다른 분들의 풀이도 한~참 바라봤던 문제.
• 내 식으로 이해한 것을 적어두긴 했는데 잘 썼는지..모르겠ㄷ..
• 스택을 써야한다는 포인트 (이거 파악이 너무 어려웠다..)
  
  • 스택에 전 요소를 쌓으면서 내꺼보다 전 요소가 커지는 시점을 파악하고 시간차를 계산해야겠다! 를 떠올려야 함.

4. 새로 알게된 것

• else-if 보다 if문 에서 continue, break, return 등 빠져나갈 수 있는 구문으로 작성하는게 더 낫다.
  가독성, 점점 헷갈려짐, 유지보수 측면
• var : 자바10부터 사용 가능한 자료형. js 같은 느낌. (js에서도 typescript 로 넘어가는 마당에 구지..? 난 잘 쓸지 모르겠다.)