[Lv.2] 프로그래머스 - 연속된 부분 수열의 합 : Java

프로그래머스

 

 

 

이해하기

• sequence라는 배열에서 sum이 k와 같은 부분 배열을 찾는다.
• 부분 배열 중 길이가 가장 짧거나 길이가 서로 같으면 앞쪽의 부분 배열을 찾는다.

이 두 가지 로직을 생각하면서 활용한 자료구조를 고민하고 List를 선택하였다.

로직은 제대로 작동했지만 제출 시 시간초과로 실패 (58.8점)

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        List<int[]> list = new ArrayList<>();
        
        int sum = 0;
        
        for (int i = 0; i < sequence.length; i++) {
            sum += sequence[i];
            
            if (sum == k) {
                list.add(new int[]{i, i});
            }
            
            for (int j = i + 1; j < sequence.length; j++) {
                sum += sequence[j];
                
                if (sum > k) {
                    sum = 0;
                    break;
                } else if (sum == k) {
                    list.add(new int[]{i, j});
                    break;
                }
            }
            
            sum = 0;
        }
        
        if (list.size() == 1) {
            return list.get(0);
        }
        
        int[] len = new int[list.size()];
        
        for (int i = 0; i < list.size(); i++) {
            int[] temp = list.get(i);
            len[i] = temp[1] - temp[0];
        }
        
        int min = Arrays.stream(len).min().getAsInt();
        
        for (int i = 0; i < len.length; i++) {
            if (len[i] == min) {
                return list.get(i);
            }
        }
        
        return answer;
    }
}

 

그래서 Map으로 다시 풀어볼까? 하고 수정한 두번째 풀이

이 또한 로직은 제대로 작동했지만 시간초과로 실패 (52.9점)

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[]{0, sequence.length - 1};
        
        int left = 0;
        int right = 1;
        
        int sum = sequence[0];
        
        while (left < right) {
            if (sum == k) {
                change(left, right, answer);
                sum -= sequence[left++];
            } else if (sum > k) {
                sum -= sequence[left++];
            } else if (right < sequence.length) {
                sum += sequence[right++];
            } else {
                break;
            }
        }
        
        return answer;
    }
    
    public void change(int left, int right, int[] answer) {
        if (right - left < answer[1] - answer[0] + 1) {
            answer[0] = left;
            answer[1] = right - 1;
        }
    }
}

 

그래서 참고한 블로그⬇️

[프로그래머스] 연속된 부분 수열의 합 Lv2 JAVA [투포인터][엄탱]

 

이 문제는 내가 풀었던 것처럼 완전탐색으로 풀면 무조건 시간초과가 떠서 투 포인터로 구현해야 한다고 한다.

 

문제풀이

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[]{0, sequence.length - 1};
        
        int left = 0;
        int right = 1;
        
        int sum = sequence[0];
        
        while (left < right) {
            if (sum == k) {
                change(left, right, answer);
                sum -= sequence[left++];
            } else if (sum > k) {
                sum -= sequence[left++];
            } else if (right < sequence.length) {
                sum += sequence[right++];
            } else {
                break;
            }
        }
        
        return answer;
    }
    
    public void change(int left, int right, int[] answer) {
        if (right - left < answer[1] - answer[0] + 1) {
            answer[0] = left;
            answer[1] = right - 1;
        }
    }
}

 

 

자료구조는 이제 좀 익숙하지만 알고리즘 공부는 더 많이 해야 할 것 같다...ㅜ