[Programmers / Level2] 178870. 연속된 부분 수열의 합(Java)

💡 Info

---

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/178870
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/178870. 연속된 부분 수열의 합

입출력 조건

---

입출력 예시

---

문제 이해

---

• 주어진 수열의 합이 k가 되었을 때의 시작과 끝 인덱스를 반환하는 문제

알고리즘

---

풀이 시간 : 20분

1. sequence의 합인 sum 선언
2. sum += sequence[j]로 합 구하기
3. sum == k라면 -> sequence.length 반환하기

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = {};
        
        int minLength = Integer.MAX_VALUE;
        
        
        for(int i=0; i<sequence.length; i++){
            int sum = 0;
            for(int j=0; j<sequence.length; j++){
                sum += sequence[j];
                
                if(sum == k){
                    if( j - i + 1 < minLength){
                        minLength = j - i + 1;
                        answer = new int[minLength];
                        System.arraycopy(sequence, i, answer, 0, minLength);
                    }
                }
                break;
            }
        }   
        return answer;
    }
}

오답체크

---

• 테스트 미통과 문제
  • start와 end를 선언하고, -1로 초기화해줘야 함.
  • 또한, j의 범위가 i부터 시작할 수 있도록 범위를 재조정해야 함.
  • answer를 0으로 초기화해 불필요한 if문을 추가로 만들지 않도록 함.

//before
for(int i=0; i<sequence.length; i++){
int sum = 0;
	for(int j=0; j<sequence.length; j++){
		sum += sequence[j];
		
        if(sum == k){
			if( j - i + 1 < minLength){
				minLength = j - i + 1;
                answer = new int[minLength];
                System.arraycopy(sequence, i, answer, 0, minLength);
            }
        }
        break;
    }
}   
return answer;

//ing
for(int i=0; i<sequence.length; i++){
	int sum = 0;
    for(int j=i; j<sequence.length; j++){
    	sum += sequence[j];
		
        if(sum == k){
			if( j - i + 1 < minLength){
            	minLength = j - i + 1;
                start = i;
                end = j;
                answer = new int[]{start, end};
            }
            break;
       }
	}
}

if(start == -1){
	return new int[0];
}

//after        
int[] answer = new int[0];
        
int minLength = Integer.MAX_VALUE;
int start = -1;
int end = -1;

for(int i=0; i<sequence.length; i++){
	int sum = 0;
    for(int j=i; j<sequence.length; j++){
    	sum += sequence[j];
                
        if(sum == k){
        	if( j - i + 1 < minLength){
            	minLength = j - i + 1;
                start = i;
                end = j;
                answer = new int[]{start, end};
            }
            break;
 		}
    }
}
return answer;

• 시간 초과 발생
  • 이중 for문 + 중첩된 if문으로 인해 시간 초과가 발생하는 것으로 확인하고, 리팩토링 진행
  • 이중 for문의 경우 -> i와 j를 밖에서 선언하여 제거
  • while문을 사용해 배열을 바로 확장하고 축소할 수 있도록 수정
  • sum == k인 경우의 minLength를 j-i로 간소화하고, 안쪽 if문의 계산도 j - i <minLength로 바로 계산하도록 간소화

        int[] answer = new int[0];
        
        int minLength = Integer.MAX_VALUE;
        
        int start = -1;
        int end = -1;
        int sum = 0;
        
        int i = 0;
        int j = 0;

        while(j < sequence.length){
            sum += sequence[j++];
            
            while(sum > k && i < j){
                sum -= sequence[i++];
            }

            if(sum == k){
                if(j - i < minLength){
                    minLength = j - i;
                    start = i;
                    end = j - 1;
                }
            }
        }
        
        answer = new int[]{start, end};
        
        return answer;
    }
}

최종 풀이

---

풀이 시간 : 1시간 7분(첫 풀이 시간 포함)

1. start 및 end 선언 및 초기화, answer 초기값은 0으로 초기화
2. sequence의 합인 sum 선언
3. sum += sequence[j++]로 합 구하기
4. sum -= sequence[i++]로 다시 축소하기
5. sum == k라면 -> sequence.length 반환하기

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[0];
        
        int minLength = Integer.MAX_VALUE;
        
        int start = -1;
        int end = -1;
        int sum = 0;
        
        int i = 0;
        int j = 0;

        while(j < sequence.length){
            sum += sequence[j++];
            
            while(sum > k && i < j){
                sum -= sequence[i++];
            }

            if(sum == k){
                if(j - i < minLength){
                    minLength = j - i;
                    start = i;
                    end = j - 1;
                }
            }
        }
        
        answer = new int[]{start, end};
        
        return answer;
    }
}

결과

🚨 참고할 풀이

• 투포인터 활용
• 출처 : [프로그래머스 Level 2] 연속된 부분 수열의 합 (Java)

class Solution {
    public int[] solution(int[] sequence, int k) {
        
        int N = sequence.length;
        int left = 0, right = N;
        int sum = 0;
        for(int L = 0, R = 0; L < N; L++) {
            while(R < N && sum < k) {
                sum += sequence[R++];
            }
            
            if(sum == k) {
                int range = R - L - 1;
                if((right - left) > range) {
                    left = L;
                    right = R - 1;
                }
            }
            
            sum -= sequence[L];
        }
        
        int[] answer = {left, right};
        
        return answer;
    }
}