프로그래머스 - 주식가격

프로그래머스 - 주식가격

본 포스팅은 java로 작성되었습니다.

이 문제는 사실 스택 단원에 있었는데.. 스택을 푸는 방법은 딱히 떠오르지 않는다..
보자마자 그냥 문자열 순회하면서 푸는 방법만 생각이 났다. 시간 복잡도가 O(N^2)이라서 효율성 테스트에서 걸릴려나 했는데 안걸렸다.. 다행(?)

이후에 스택으로 푸는 방법도 추가하겠다.

---

1. 접근 방법

그냥 예시를 보면서 가장 먼저 든 생각은, 문자열을 순회하다가
현재 인덱스보다 크거나 같은 값을 만났다면 count++, 작은값을 만났다면 바로 break하는 방법이다.

딱히 어려운 것은 없었고.. 그냥.. 구현했다.
하나 좀 주의(?) 해야할 점은 다음 인덱스로 넘어갔을 때, 검사를 하고 count++ 하는 것이 아니라 어쨌든 1초라도 유지되었다는 점에서 먼저 count++을 해줘야 한다는 점이다.

2. 최종 코드

public class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i + 1; j < n; j++) {
                count++;
                if (prices[j] < prices[i]) {
                    break;
                }
            }
            answer[i] = count;
        }

        return answer;
    }
}

스택으로 푸는 법은 추후.. 작성하겠다