백준 - 4097. 수익

알고리즘과 자바에 대해 다시 상기시키고 싶어서 다시 PS를 시작하고자 한다.

 

4097. 수익

https://www.acmicpc.net/problem/4097

 

문제

 

설명

첫째 줄에 N, 둘째 줄부터 N개의 줄엔 수익 P가 주어진다. 범위는 N은 250,000까지, P는 -10,000 ~ 10,000까지이다.

다만 테스트 케이스 개수는 정해지지 않아서 O(N)에 구현하는 것을 목표로 고민했다.

 

접근 1

구간에 대해 가장 큰 값을 구하는 것은 어렵지 않았다. 합이 음수가 되는 순간 가장 큰 값이 아니게 되기 때문이다.

고민했던 부분은 구간이 비어있으면 안 된다는 조건이다.

 

반목문을 통해 값을 더해갔는데, 최초 값을 반복문 밖으로 빼서 받을지, 첫 입력인지에 대한 Flag를 둘지 고민했고, 후자로 결정했다. 

 

풀이 코드

import java.io.*;

public class Main {
    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int input;
        while ((input = Integer.parseInt(br.readLine())) != 0) {
            sb.append(getMaxValue(input)).append('\n');
        }
        System.out.print(sb);
    }

    private static int getMaxValue(int size) throws IOException {
        boolean isFirst = true;
        int max = 0;
        int sum = 0;

        while (size-- > 0) {
            int current = Integer.parseInt(br.readLine());
            sum += current;

            if (max < sum || isFirst) {
                max = sum;
                isFirst = false;
            }

            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
}

 

나름 Java 풀이 중 높은 등수라서 만족했다.

 

접근 2

문제 풀이 후 글을 작성하면서 다른 방법이 떠올랐다.

P의 최솟값이 -10,000이므로 max를 이보다 더 작게 초기화하면 Flag가 필요 없어지는 것이다.

아래 코드와 같이 `isFirst` 를 없애고 max를 -10001로 초기화했다.

 

풀이 코드

import java.io.*;

public class Main {
    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int input;
        while ((input = Integer.parseInt(br.readLine())) != 0) {
            sb.append(getMaxValue(input)).append('\n');
        }
        System.out.print(sb);
    }

    private static int getMaxValue(int size) throws IOException {
        int max = -10001;
        int sum = 0;

        while (size-- > 0) {
            int current = Integer.parseInt(br.readLine());
            sum += current;

            if (max < sum) {
                max = sum;
            }

            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
}

 

결과는 더 느리다..? 흠..