연속된 부분 수열의 합

링크텍스트

문제 설명

1. 순서대로 숫자를 더해갔을 때 k가 되는 순간의 시작 인덱스, 끝 인덱스를 answer에 반환
2. 이때 길이가 가장 짧은 인덱스로 선택
   2-1. 2번째 예시에서 5가 되는 것이 [1112], [23], [5] 다. 여기서 길이가 가장 짧은 것은 [5]이다. 그러므로 answer은 [6,6]임.
3. 길이가 같다면 인덱스가 작은 것이 나와야 한다.
   3-1. 3번째 예시에서 6이 되는 것은 [222], [222], [222] 이다. 그럼 인덱스0부터 인덱스2가 가장 작은 인덱스이므로 answer은 [0,2]임.

시행착오 및 문제 풀이

오답 풀이

1. 이중 for문을 사용하여 순서대로 num에 sequence의 값을 더해간다.
2. 이때 num이 k와 같아진다면 배열의 길이를 구한다(len). max_len은 가장 길 때의 값을 넣어주었고 len과 max_len을 비교하였을 때, 더 짧으면 인덱스의 값을 갱신해준다. 그러고 최대 길이를 현재의 길이로 갱신해준다.
   효율성을 위해 더 이상 계산이 필요하지 않은 경우 break 해준다.
3. num이 k를 넘어가버리면 답이 아니므로 바로 break 해준다.

오답 코드

import java.util.*;
class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int max_len = sequence.length;
        
        for(int i=0; i<sequence.length; i++) {
            int num = 0;
            
            for(int j=i; j<sequence.length; j++) {
                num += sequence[j];
                
                if(num == k) {
                    //길이가 짧은 수열이 나와야 함 && 길이가 같다면 앞쪽 인덱스가 나와야 함
                    int len = j-i;
                    
                    if(len < max_len) {
                        answer[0] = i;
                        answer[1] = j;
                        max_len = len;
                        break;
                    }
                }
                
                else if(num > k) {
                    break;
                }
            }
        }
        return answer;
    }
}

사실 조건을 대충 봐서 sequence의 길이가 아닌 원소의 범위를 봤다. 1000까지 이길래 "오~ 이중 for문 가능가능ㅎㅎ" 하고 풀었음ㅜㅜㅜ
암튼 효율성 엉망으로 나와서 58점인가.... 암튼 실패 떼잉

정답 풀이

비법은 투포인터~ (몰랐어)

1. right 변수는 sequence 배열의 시작부터 오른쪽으로 가면서 sum 변수에 더해지는 변수이다.
   left 변수는 sum변수가 k를 넘었을 경우 왼쪽에서부터 차례대로 빼 줄 변수이다. (왼쪽->오른쪽으로 줄어든다)
   max_len 변수는 최대 길이를 저장한 변수이고, ans1과 ans2는 각각 left와 right의 최솟값을 저장하기 위한 변수이다.
2. sum에 sequence[right]를 더해주다가 k를 넘어버리면 sequence[left]를 k보다 작거나 같아질때까지 빼준다.
3. k와 같아진다면
   3-1. 길이가 더 짧은 인덱스가 나와야 한다. 길이가 max_len보다 짧다면 ans1, ans2 갱신해준다. max_len도 현재의 배열 길이로 갱신해준다.
   3-2. 길이가 같다면 앞쪽의 인덱스가 나와야 한다. Math.min으로 최솟값 넣어준다.
4. answer에 ans1, ans2값 넣어주고 반환

정답 코드

//투포인터
import java.util.*;
class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        
        int left = 0;
        int sum = 0;
        int max_len = sequence.length;
        
        int ans1 = 0;
        int ans2 = 0;
        
        for(int right = 0; right<sequence.length; right++) {
            sum += sequence[right];
            
            //합이 k를 넘어버리면 왼쪽(left)에서 하나씩 빼주기
            if(sum > k) {
                while(sum > k) {
                    sum -= sequence[left];
                    left++;
                }
            }
            //k와 같다면
            if(sum == k) {
                //길이가 짧은 인덱스가 나와야 함
                int len = right-left;
                
                if(len < max_len) {
                    ans1 = left;
                    ans2 = right;
                    max_len = len;
                }
                //길이가 같다면 앞쪽의 인덱스가 나와야 함
                else if(len == max_len) {
                    ans1 = Math.min(ans1, left);
                    ans2 = Math.min(ans2, right);
                }
            }
        }
        
        answer[0] = ans1;
        answer[1] = ans2;
        
        return answer;
    }
}

정답!
투포인터 문제...!! 막상 풀면 쉬운데 투포인터를 떠올리기가 쉽지 않다. 많이 풀면 자연스럽게 생각나겠지 모~

---

왜 항상 예시코드는 돌아갈까? 희망고문이다. 시험칠 때는 정답 못돌려보잖아 그럼 나 맞췄다 생각하고 기분 좋게 넘어갈 거 아냐 하........

• 조건 잘 보기
• 효율성 항상 생각하기