프로그래머스 - 연속 펄스 부분 수열의 합 + 구간 합

프로그래머스 - 연속 펄스 부분 수열의 합 lv3 문제를 풀어보았고, 문제를 풀면서 공부한 구간 합에 대해서도 정리해 본다.

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=java 

프로그래머스

풀이 시간: 1시간

---

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=java

제한사항

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=java

이 문제를 보고 배열이 주어졌을 때 특정 구간의 연속 수열에 펄스 값을 곱하고 그 합이 최대가 되는 것을 찾는 문제라고 이해했다.

처음 생각한 아이디어는

• 배열의 길이가 50만이므로 n^2으로 풀 수 없다.
• 투 포인터 문제로 생각이 들어 부분 수열의 시작지점과 끝 지점을 나눠 탐색
• 양 옆의 숫자의 부호가 다르면 최댓값을 만들 수 있겠다
• 그렇다면 부호가 같으면 그 합이 최대면 저장하고 아니면 다음 수부터 새로운 부분수열을 시작하자

이렇게 생각하고 처음엔 투 포인터 방향으로 코드를 진행했다.

 

코드를 짜다가 반례가 생각났다. 부호가 같은 수가 나오더라도 3 -1 -1 -3와 같이 나오게 되면 3 -1 -1보다 더 값이 커진다. 따라서 모든 구간의 합을 알아야 한다고 생각을 바꾸었다.

 

---

구간 합

 

구간 합 알고리즘은 합 배열을 사용하여 특정 구간의 합을 구할 수 있는 방법이다.

 

예를 들면

 

[5,4,3,5,7,8,9]와 같은 배열이 존재하면 이에 대한 합 배열을 생성

sumArr = {0,5,9,12,18,25,33,42}를 만들 수 있다. 합 배열의 경우 주어진 배열보다 길이가 1 더 커야 한다. (아무것도 더하지 않은 경우)

 

합 배열을 이용한 구간 합 구하기

 

sumArr의 각 인덱스는 

• 0번 인덱스: 아무것도 더하지 않음
• 1번 인덱스: 맨 첫 원소를 더함
• 2번 인덱스: 맨 첫 원소와 두 번째 원소를 더함
• ...

따라서 sumArr[4] - sumArr[2]를 하게 된다면? 3번과 4번 원소의 합을 구하는 우리가 원하는 구간의 합을 구할 수 있다.

 

원하는 구간k~l의 합 = sumArr[l] - sumArr[k]의 식으로 나타낼 수 있고 특정 구간의 합을 O(1)에 얻을 수 있다.

 

이를 설명하기 좋은 그림이 있어 첨부한다.

참조 링크

[알고리즘] 접두사합(prefix sum) 알고리즘(구간의 합)

---

문제 풀이

 

다시 문제로 돌아와서 생각한 풀이를 정리하면

• 50만 제한사항으로 인해 O(n^2)이 불가능 하다
• 합배열을 이용해 구간 합을 구하면 연속 부분 수열에 대한 최댓값을 찾을 수 있다.
• 연속 부분 수열에 대한 최댓값을 찾을 때 투 포인터 알고리즘을 활용하자
• 1,-1 혹은 -1,1이 반복되는 펄스값이 곱해져야 하므로 두 개의 합 배열을 만들고 각 구간 합에서 최대값을 찾으면 된다.

풀이 코드

import java.util.*;
class Solution {
    public long solution(int[] sequence) {
        if(sequence.length == 1) return Math.abs(sequence[0]);
        long[] s1 = makeSumArr(sequence, 1);
        long[] s2 = makeSumArr(sequence, -1);
        return Math.max(findMaxPartialSequence(s1), findMaxPartialSequence(s2));
    }
    public long findMaxPartialSequence(long[] sumArr){
        long max = Long.MIN_VALUE;
        int st = 0;
        int en = 1;
        while(en<sumArr.length){
            long sum = sumArr[en] - sumArr[st];
            if(sum >= 0){
                max = Math.max(max, sum);
            }
            else st = en;   // 구간합이 음수
            en += 1;
        }
        return max;
    }
    public long[] makeSumArr(int[] sequence, int perse){
        long[] sumArr = new long[sequence.length + 1];
        for(int i=0; i<sequence.length; i++){
            sumArr[i+1] = sumArr[i] + sequence[i] * perse;
            perse *= -1;
        }
        return sumArr;
    }
}

설명

• makaeSumArr 메서드를 정의하여 합 배열을 만들고, 시작 펄스값을 전달
• findMaxPartialSequence에서 투 포인터 st, en을 만들고 st ~ en의 구간합을 구한다.
  
  • 초기값이 st = 0, en = 1 이면 첫 번째 원소에 대한 구간 합이 되는 것이다. (첫 번째 원소를 더한 값 - 0)
  • st = 0, en = 2가 되면 첫 번째 원소 + 두 번째 원소의 합이 되는 것이다.(두 번째 원소까지의 합 - 0)
  • st = 1, en = 3가 되면 세 번째, 두 번째 원소의 합이 되는 것이다. (세 번째 원소까지의 합 - 첫 번째 원소까지의 합)
• 구간 합이 음수라는 것은 sumArr[en]이 sumArr[st]보다 작다는 의미
  • 그렇다면 첫 번째 원소부터 sumArr[st]까지의 구간 합 중 이미 앞에서 최댓값을 저장했을 것(sum>=0)
  • st를 한 칸 앞으로 옮겨서 sumArr[en] ~ sumArr[st+1}을 비교할 필요가 없음
    • 합 배열이 펄스 값을 곱하면서 st -> en까지 합이 작아지는 구간이라는 의미이기 때문에
  • en위치에서 새로운 구간을 합을 비교해야 한다.

---

참고 영상:

구간 합 알고리즘 설명 강의

https://www.youtube.com/watch?v=O514yiWg8YE&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=10