[백준 - 11501] 주식 - Java

문제 설명

 

11501번: 주식

 

풀이 회고

해당 문제에서 요구하는 것은 일자별로 주가가 주어졌을 때 주식을 샀다 팔았다(단타) 해서 낼 수 있는 최대 이익을 구하는 것입니다. 즉, 핵심은 쌀 때 사서 비쌀 때 파는 것입니다.

 

해당 문제에서 두고 있는 시간 제한은 5초로 다소 여유(?) 있다고 생각했었습니다. 그리하여 처음에는 단순 무식한 방법으로 2중 for문을 통해 문제에 접근했었습니다..😅 일자별 주식을 그 이후의 주식의 가격과 일일이 비교해보면서 가장 비싼 주식을 찾아 그 주식과의 가격 차이를 구해 합계(result)에 더하는 방식이었습니다. 

 

하지만 문제에서 주어진 "날 수"는 최대 1백만으로, 2중 for문 시 최대 1조번의 연산이 발생하므로 5초라는 시간으로는 턱없이 부족합니다. 이에 대한 입력부와 출력부를 제외한 주요 로직은 다음과 같습니다.

 

    public static long trade() {
        long result = 0;
        int buy, sell;

        for (int i = 0; i < days; i++) {
            buy = prices[i];
            sell = buy;
            for (int j = i + 1; j < days; j++) {
                if (sell < prices[j]) {
                    sell = prices[j];
                }
            }
            if (sell > buy)
                result += sell - buy;
        }

        return result;
    }

 

 

그리하여 이 보다 효율성을 높일 수 있는 방법을 생각해보았는데, "어떻게 하면 2번째 for문을 최소화할 수 있을까?"에 대해 고민해보았습니다. 이에 대해 생각한 방법으로는 주어진 일자별 주가 중 가장 비싼 주식을 찾아, 그 이전의 주식들은 당연히 이 가장 비싼 주식 보다 싼 가격이므로 2번째 for문을 거치지 않고 차액을 구해 바로 합계에 더해주는 방식을 취해보았습니다. 이에 대한 입력부와 출력부를 제외한 주요 로직은 다음과 같습니다.

 

    public static long trade() {
        long result = 0;
        int buy, sell = 0, index = -1;

        for (int i = 0; i < days; i++) {
            buy = prices[i];
            if (i <= index) {
                result += sell - buy;
                continue;
            }

            sell = buy;
            for (int j = i + 1; j < days; j++) {
                if (prices[j] > sell) {
                    sell = prices[j];
                    index = j;
                }
            }

            if (sell > buy)
                result += sell - buy;
        }

        return result;
    }

 

 

확실히 이전보다 시간복잡도 효율성은 많이 개선 되었지만 문제의 요건을 완전히 충족시킬 수는 없었습니다. 어떻게 하면 2번째 for문을 더욱 적게 사용할 수 있을까 고민해봤지만, 특별히 떠오르는 아이디어가 떠오르지 않았습니다. 그리하여 결국 힌트를 얻기 위해 해당 문제에 대한 백준 게시판을 찾던 중 "뒤에서 부터 탐색하는 방법"을 확인할 수 있었습니다.

 

무슨 말이냐면 주어진 일자별 주식을 뒤에서부터 탐색하여 그때 그때 최대값을 구하고 그 직전 값이 앞서 구했던 최대값보다 작으면 차익을 구해 합계를 더하는 방식입니다. 이에 대한 입력부와 출력부를 제외한 주요 로직은 다음과 같습니다.

 

    public static long trade() {
        long result = 0;
        int max = 0;

        for (int j = days - 1; j >= 0; j--) {
            if (prices[j] > max) {
                max = prices[j];
            }
            else {
                result += max - prices[j];
            }
        }

        return result;
    }

 

예를 들어 6일이라는 기간 동안 주식의 가격이 1, 2, 6, 1, 2, 3이라고 했을 때, 뒤에서부터 탐색하여 최초에 발견된 3을 우선 최대값으로 두고 그 이후에 나오는 주식의 가격과 비교하는데, 이는 2이므로 3보다 작으므로 2에서 사서 3에서 팔아 최대 이익을 남길 수 있습니다. 그 이후에는 1이 발견되는데, 이 역시 3보다 작으므로 3에서 팔아 2라는 최대 이익을 남길 수 있습니다. 그 다음에는 6이 발견되는데, 이는 3보다 크므로 이 6을 최대값을 두고 다시 탐색을 시작합니다. (6에 사서 3에 파는 것은 손해!!) 이러한 방식으로 접근하면 단일 for문 즉, 시간복잡도 O(N)으로 문제를 해결할 수 있습니다.

 

 

개선해야 할 점

저의 기존 방식은 일자별 주식을 그 이후에 등장하는 가장 비싼 주식을 찾아 차익을 더해 합해주는 방식이었고 이를 개선하여 2번째 for문을 최소화 했을지라도 이는 결국에 2중 for문이라는 틀에 갇혀있는 방식이었습니다. 결론적으로 제가 이 문제를 스스로 해결할 수 없었던 이유는 제 생각이 이 2중 for문이라는 틀에 갇혀 있었기 때문이었습니다. 이렇게 2중 for문이라는 틀에 갇혀서 효율성을 생각하다보니 성능 개선이 부족했습니다. 이번 문제를 통해 문제 해결 관점에 있어서 특정(하나의) 생각에 너무 매몰되기 보다는 다른 관점으로도 생각해봐야할 필요성을 느낄 수 있었습니다.

 

 

참고자료

• https://www.acmicpc.net/problem/11501