[프로그래머스] 연속 펄스 부분 수열의 합 | Java - 민민의 하드디스크 - 티스토리

연속 펄스 부분 수열의 합

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

제한 사항

1 ≤ sequence의 길이 ≤ 500,000
-100,000 ≤ sequence의 원소 ≤ 100,000
sequence의 원소는 정수입니다.

입출력 예

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

 

코드 1

class Solution {
    public long solution(int[] sequence) {
        long max = Long.MIN_VALUE;
        long min = Long.MAX_VALUE;
        long sum = 0;

        for (int i = 0; i < sequence.length; i++) {
            sum += (long) sequence[i] * (i % 2 == 0 ? 1 : -1);
            max = Math.max(max, sum);
            min = Math.min(min, sum);
        }

        return Math.abs(max - min);
    }
}

 

결과 1

 

 

코드 2 (정답 코드)

728x90

class Solution {
    public long solution(int[] sequence) {
        long max = 0;
        long min = 0;
        long sum = 0;

        for (int i = 0; i < sequence.length; i++) {
            sum += (long) (sequence[i] * (i % 2 == 0 ? 1 : -1));
            max = Math.max(max, sum);
            min = Math.min(min, sum);
        }

        return Math.abs(max - min);
    }
}

풀이

for (int i = 0; i < sequence.length; i++) {
    sum += (long) sequence[i] * (i % 2 == 0 ? 1 : -1);
    max = Math.max(max, sum);
    min = Math.min(min, sum);
}

• sequence 인덱스가 짝수이면 더하고, 홀수이면 뺌
• 현재까지의 최대, 최소값을 각각 max, min에 저장하고
• 절대값을 씌워서 뺀 값을 return 

return Math.abs(max - min);

결과