[PS] 프로그래머스 Lv2 : 연속된 부분 수열의 합(Java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

---

풀이

정석적인 구간합 풀이 (투포인터)

 

접근법

문제를 조금 읽어보면 알 수 있듯, 특정 합(k)을 만족하는 구간을 구하는 문제로 구간합을 구하는 알고리즘을 적용해서 풀 수 있다.

처음에 떠올린 방법은 투포인터를 활용해서 구간합 조건을 검색하는 방식이였고, 두번째는 누적합이다.

만약 '비내림차순'이 아니라 정렬이 되어 있다는 가정이라면 이분탐색을 활용해도 풀 수 있다.

 

우선 해당 문제의 조건은 간단하다. 만족하는 구간합이 여러 CASE일 경우 아래 조건에 따라 해를 구해야하는 조건뿐이다.

1. 구간합의 길이가 짧은 수열

2. (길이도 같다면) 시작 인덱스가 작은 수열

또한 주어지는 배열 sequence의 길이는 최대 1,000,000까지 나오므로 시간복잡도의 경우 최대 O(N)까지 가능하다.

 

완전탐색 (그리디)

먼저 정해를 찾기 이전에 시간복잡도를 신경쓰지 않고, 간단하게 구간합을 구하는 방법은 완전탐색으로 찾을 수 있다.

예로 특정 인덱스 i의 위치에서 0 ~ i-1 까지 앞쪽 인덱스를 한개씩 빼면서 합이 k를 만족하는지 구하면 된다.

이 경우에는 두번의 반복문으로 시간복잡도가 O(N^2)이 되기 때문에 풀리지 않는다.

 

투포인터 (아래 소스코드 첨부)

투포인터는 구간합을 구하는 경우에 주로 사용하는 대표적인 알고리즘이다.

원리는 간단하다. 먼저 두 개의 포인터를 구간합의 왼쪽 오른쪽이라고 가정한다. 그 후 아래 조건에 따라 포인터를 이동시켜나간다.

1. 구간합이 k보다 작으면 오른쪽 포인터를 이동시켜 값을 키워준다.
2. 구간합이 k보다 크면 왼쪽 포인터를 이동시켜 값을 줄여준다. 

포인터를 이동시킬때마다 k와 비교하여 정답을 찾으면 된다.

해당 문제에서는 단순 구간합을 묻고 있기 때문에 포인터의 초기 위치는 왼쪽 끝에서 시작해서 오른쪽으로 이동시켜나가면 된다.

 

투포인터에 대한 추가적인 자료는 아래를 참고하면 도움이 될 듯 하다.

https://infinitecode.tistory.com/76

[PS] 백준2003 : 수들의 합 2(JAVA) - 투 포인터 활용편

 

누적합

그리고 누적합도 처음에 생각을 했었다고 말했는데, 투포인터 풀이 뒤에 한번 시도해봤지만 해당 문제에서는 적용이 안된다.

다른 방식도 있겠지만 정석 누적합으로 초기 누적합 배열 sum을 구한 후, 특정 구간의 합을 한번에 조회하는 방식으로 적용했는데 이 또한 시간복잡도가 O(N^2)이 되기 때문에 시간초과가 발생한다.

 

구간합 문제에 누적합을 적용하기 위해서는 같은 구간의 합을 N번 반복하는 조회 문제가 되어야할거 같다.

해당 문제는 전체 구간을 1번만 탐색하면 되는 문제이기 때문에 투포인터로 접근하는게 맞다.

---

소스코드

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] res = new int[2];
        
        /**
        <정석적인 구간합 문제>
        1. 길이가 짧은 수열 > 시작 인덱스가 낮은.
        방법 1. 투포인터 : right를 늘리면서 커지면 left를 당기는 방식 -> 풀이완
        **/
        
        int l=0, r=0, sum=sequence[0], min=Integer.MAX_VALUE;
        
        while(l<sequence.length) {
            if(sum == k) {
                if(r-l < min) { // 시작 인덱스 조건절
                    res[0] = l; res[1] = r;
                    min = r-l;
                }
            }
            
            if(sum > k){
                sum -= sequence[l++];
            }
            else {
                if(r+1 >= sequence.length) break;
                sum += sequence[++r];
            }
        }
        
        return res;
    }
}

---

정리

최근 알고리즘 문제를 안풀기도 했고, 풀어도 시뮬레이션쪽으로만 풀었더니 누적합이라는 잘못된 접근도 했던게 아닌가 싶다..

듣기에는 요즘 기업 코딩테스트 트렌드가 시뮬레이션(or 구현)쪽으로 많이 바뀌는것 같다고 하는데, 한번씩 특정 알고리즘 문제 푸는것도 나쁘지 않을것 같다.

 

추가로 위 정답코드는 몇번의 리팩토링이 있었는데, 처음 제출한 코드는 생각보다 너무 더럽기도 했고 조건문이 덕지덕지 붙어있어서 깔끔하게 만들어봤다...

개발할때도 그렇고 문제 풀때도 그렇고 조금은 깔끔하게 작성하고 싶은데, 그냥 생각나는대로 코드 써내려가는게 습관이 되어서 고쳐야할 문제중에 하나... 회사 복지로 클린코드라는 책을 사놓긴 했는데 얼른 읽고 깔끔한 코드를 작성할 수 있도록 노력해야겠다 :)