연속된 부분 수열의 합 [자바]

 

🧫 문제 분석

✔️ 출처

연속된 부분 수열의 합 level 2

📖 문제

 

비 내림차순 정렬 : 오름차순 정렬

 

흔한 투 포인터 문제이다.

 

투 포인터로 값을 합산하고 k와 비교하여 크다면 앞 포인터를 움직이고 그만큼 빼고,

작다면 뒤 포인터를 움직이고 그만큼 더한다.

 

짧은 길이의 수열 인덱스만 갖는 배열을 준비한다. 

배열의 길이가 100만까지니까 1000001 까지 해서 최댓값으로 초기에 설정한다. 

 

투 포인터의 합계가 k와 같다면 앞 포인터 인덱스 - 뒤 포인터 인덱스 한 값이 짧은 길이의 수열 인덱스 배열과 비교하여 가장 짧은지 확인하는데 같다면 넘어가고, 더 짧다면 갱신해주면된다.

 

자세한건 코드를 참조

 

 

 

 

---

🔅 문제 풀이

class Solution {
    // 투 포인터 문제 예상
    // 연속된 부분 수열의 합
    // 비 내림차순 정렬 -> 오름차순 정렬 
    
    public int[] solution(int[] sequence, int k) {
        
        int[] answer = {0, 10000001};
        
        // 투 포인터 및 합 변수 선언, 초기화
        int front = 0;
        int back = 0;
        int sum = 0;
        
        while(front < sequence.length 
              || back < sequence.length ) {

            if (sum < k) {
                // sum < k 인 상황에서 back이 이미 끝까지 갔으면 의미 없기에 종료
                if (back >= sequence.length) break;
                sum += sequence[back];
                back++;
                
            } else if (sum > k) {
                sum -= sequence[front];
                front++;
            
                // k == sum
            } else {
                // 부분 수열의 합 길이가 더 짧다면 
                if (answer[1] - answer[0] > (back - 1) - front) {
                    answer[0] = front;
                    answer[1] = back - 1;
                }
                // 같았을 때 처리후 else문으로 다시 들어오는것을 방지
                sum -= sequence[front];
                front++;
            }   
        }
        return answer;
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. 알고리즘은 잘 짰는데 문제의 sequence 길이를 제대로 안봐서 의미없는 삽질을 조금 했다. 부끄럽다..