[프로그래머스] 연속된 부분 수열의 합 / 자바

문제         

프로그래머스

1 번째 시도   

 

• 시작 인덱스를 i 끝 인덱스를 j 로 가정한다.
• i를 고정하고 j를 올려가면 총합을 올려간다.
• 만약 i ~ j 의 합이 주어진 k와 같거나 크다면 반복문을 멈춘단. 같다면 멈추고 i와j의 길이, i, j를 기록한다.
• i +1 하고 2 ~ 3 과정을 반복한다.
• 기록한 것들을 조건에 부합하게 정렬한다.
• 가장 앞에 있는 인덱스를 꺼낸다.

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int n = sequence.length;
        int[] answer = new int[2];

        ArrayList<int[]> list = new ArrayList<>();    
    
        for (int i = 0; i < n; i++) {
            int sum = 0;
            int one = -1;
            int two = -1;            
            for (int j = i; j < n; j++) {
                sum += sequence[j];
                if (sum > k) {
                    break;
                }
                else if(sum == k) {
                    one = i;
                    two = j;
                      list.add(new int[]{j - i, i, j}); 
                    break;
                }
            }
        }
        
        Collections.sort(list, new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0])
                    return o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });
        
        
        answer[0] = list.get(0)[1];
        answer[1] = list.get(0)[2];

        return answer;
    }
}

실패는 없었지만 시간초과가 너무 많이 떴다.
그럴만도 한게

5 ≤ sequence의 길이 ≤ 1,000,000 이기 때문에

O(n2)으로 문제를 풀면 시간초과 당연히 뜬다.

 

완전탐색이 아닌 DP로 풀어야 할 것 같은 감이다.

2 번째 시도  

 

DP란 탐색을 하다 현재의 영향을 미치 것 같은 이전의 값을 저장해놓음으로 탐색 시간을 줄이는 거라 생각한다!

(아니라면 댓글 남겨주세요)

sequence {1,2,3,4,5}  k = 7 일 때를 예시를 들어보겠다.

• {1}    sum = 1    i = 0  j = 0
• {1,2}  sum =3  i = 0  j = 1
• {1,2,3}    sum =6  i = 0  j = 2
• {1,2,3,4}   sum = 10  i = 0  j = 3       
•  sum이 7을 넘었으므로 반복문 break 그리고 {2} i =1 j = 1부터 시작하는 게 아니라 맨 앞에 인덱스만 뺀 {2,3,4}  i = 1 j = 3부터 시작한다.
• 여기서 의문이 들 수도 있다.
• 중간 값 {2,3}이 만약에 k에 부합할 수도 있지 않냐?
• 그럴리가 없다. 가정을 해보자 k가 5라고 해보자.
• {1,2,3}에서 멈추고 { 2,3} 시작한다. 정답이다.
• 이번에는 예시를 작은 값으로 들어보겠다. k를 4로해보자
• {1,2,3}에서 멈추고 {2,3}이다
• {2,3}는 4보다 넘치므로  멈추고 {3}으로 시작한다. 
• 만약 {2,3}이 k에 부합했다면 {1,2,3}하고 4까지 가지 않고 여기서 멈추고 다음단계로 넘어갔을 것이다.
• 결론은 7로 합산된 배열인 경우 알고리즘은 이전 단계에서 이를 찾았을 것다.

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int n = sequence.length;
        int[] answer = new int[2];

        ArrayList<int[]> list = new ArrayList<>();

        int presentJ = 0;
        int nextSum = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            if (i != 0) {
                sum = nextSum;
            }
            for (int j = presentJ; j < n; j++) {
                sum += sequence[j];
                if (sum > k) {
                    nextSum = sum - sequence[i] - sequence[j];
                    presentJ = j;
                    break;
                } else if (sum == k) {
                    nextSum = sum - sequence[i] - sequence[j];
                    presentJ = j;
                    list.add(new int[]{j - i, i, j});
                    break;
                }
            }
        }

        Collections.sort(list, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0])
                    return o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });

        
        answer[0] = list.get(0)[1];
        answer[1] = list.get(0)[2];


        return answer;
    }
}

다른 사람 코드   

다른 사람은 나와 같은 방식으로 풀긴했지만 이 알고리즘의 이름이 DP가 아닌 투포인터라고 했다. 

k보다 작다면 오른쪽 포인터를 움직이고 k보다 크다면 왼쪽 포인터를 움직인다.

 

내 코드보다 훨씬 간결하고 시간도 빠르다. 이번 문제를 통해서 투포인터를 공부할 수 있었다.

class Solution {
    public int[] solution(int[] sequence, int k) {        

    	int left = 0;
    	int right = 0;
    	int sum = 0;
    	int size = sequence.length;
    	int ans1 = 0;
    	int ans2 = 0;
    	
    	for(right=0; right<sequence.length; right++) {    		
    		sum += sequence[right];
    		
    		while(sum > k) {
    			sum -= sequence[left];
    			left++;
    		}
    		
    		if(sum == k) {
    			if(size > right-left) {
    				size = right-left;
    				ans1 = left;
    				ans2 = right;
    			}
    			else if(size == right-left) {
    				ans1 = Math.min(ans1, left);
    				ans2 = Math.min(ans2, right);
    			}
    		}
    		
    	}
    	
    	return new int[] {ans1, ans2};
    }
}

링크: https://mag1c.tistory.com/305