문제

오답 코드 (시간 초과)

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0,0};
        int min = 1000000000; // 문제의 최댓값을 min으로 선언
        
        Map<Integer, Integer> map = new HashMap<>();
        
        // 이중for문을 돌리며 k가 되는 배열의 인덱스(앞,뒤)를 map에 답아준다 
        for(int i=0;i<sequence.length;i++) {
            int num = 0;
            a: for(int j=i;j<sequence.length;j++) {
                num += sequence[j];
                if(num==k) {
                    map.put(i,j);
                    num=0;
                    break a;
                }
            }
        }
        
        // map에서 최소 길이 비교
        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
            int front = entry.getKey();
            int back = entry.getValue();
            if((back-front) < min) { // < 로 설정했기 때문에 길이가 같다면 인덱스가 작은 값이 answer에 들어감
                min = back-front;
                answer[1]=back;
                answer[0]=front;
            }
        }        
        
        return answer;
    }
}

무지성 for문의 결과.

테스트코드는 잘 돌아갔지만 제출시 시간 초과가 나왔다.

어떻게 해야할지 감이 오지 않아 검색했다.

그리고 찾은 '투 포인터 기법'

투 포인터 기법: 배열을 순회하면서 두 개의 포인터를 사용하여 합이 k가 되는 부분 배열을 찾을 수 있습니다. 두 포인터를 사용하여 부분 배열의 시작과 끝을 조절하면서 합을 계산합니다.

while문으로 사용된 예시를 확인하고 내 코드에 적용시켜 보았다.

정답 코드

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0,0};
        int min = 1000000000;
        
        int start=0;
        int end=0;
        int num=0;
        
        Map<Integer, Integer> map = new HashMap<>();
        
        while(start<sequence.length) {
            
            // num이 k보다 작다면 end의 값을 추가하고 end를 증가
            while(end<sequence.length && num<k) {
                num+=sequence[end];
                end++;
            }

			// 합이 k라면 map에 담기
            if(num==k) {
                map.put(start,end);
            }
            
            // start 포인트를 뒤로 옮긴다
            num -= sequence[start];
            start++;
        }
        
        // map에 넣어둔 값 비교
        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
            int front = entry.getKey();
            int back = entry.getValue();
            if((back-front) < min) {
                min = back-front;
                answer[1]=back-1;  // 주의!! end에 1이 증가된 값이므로 -1 해줘야함.
                answer[0]=front;
            }
        }        
        
        return answer;
    }
}

for문으로 숫자를 전부 다 조회하는 것이 아니라,
투 포인터 기법으로 순차적으로 탐색함으로써 성능을 향상 시킬 수 있었다!

하지만 아직 아쉽다.

1. Map을 사용하지 않고도 바로 비교해서 답을 찾을 수 있을 것이다.

2. 추가적으로, int의 Max값을 int min = Integer.MAX_VALUE로 설정 할 수 있다. (2^31 - 1로 설정)

코드 개선

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {0,0};
        int min = Integer.MAX_VALUE;
        
        int start=0;
        int end=0;
        int num=0;
        
        while(start<sequence.length) {
            
            while(end<sequence.length && num<k) {
                num+=sequence[end];
                end++;
            }

            if(num==k && end-start<min) {
                min = end-start;
                answer[1] = end-1;
                answer[0] = start;
            }
            
            num -= sequence[start];
            start++;
        }
        
        return answer;
    }
}

while문에서 min값을 바로 비교함으로써 속도도 향상되고 코드도 깔끔해졌다!

다른 사람 풀이

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] result = new int[2];
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

        while (right < sequence.length) {
            sum += sequence[right];

            while (sum >= k) {
                if (sum == k && (right - left) < minLength) {
                    minLength = right - left;
                    result[0] = left;
                    result[1] = right;
                }
                sum -= sequence[left];
                left++;
            }
            right++;
        }

        return result;
    }
}

방식은 다양했지만,
다른 사람들도 똑같이 투 포인터 기법을 사용하여 풀이했다.

이러한 기법만 알고 있다면 다음번엔 당황하지 않고 풀어낼 수 있을 것 같다.