프로그래머스 - 연속된 부분 수열의 합(Java)

By on January 22, 2024

프로그래머스 - 연속된 부분 수열의 합(Java)

문제 링크 : 부분 수열의 합

이번 문제는 연속된 수열(sequence) 에서 부분 수열의 합이 k 가 되는 연속된 부분 수열을 찾는 문에 입니다.

처음에는 단순하게 dps 로 풀려고 시도 하였으나 시간 복잡도를 고려 하지 않아서 시간 초과가 발생 하여 투포인터 알고리즘을 통해 O(n) 으로 해결 하였습니다.

문제 해결 접근법(투포인터 알고리즘)

문제를 해결하기 위한 접근 방법은 다음과 같습니다.

  • 두개의 포인터(start, end) 생성
  • end 포인터를 한칸씩 이동 하면서 수를 누적 하여 더한다(currentSum)
  • 누적된 합(currentSum) 이 K 와 같다면 해당 포인터 값을 기록 한다.
  • 누적된 합(currentSum) 이 K 보가 크면 start 포인터를 한칸 이동 하면서 해당 값을 누적 값에서 빼준다.
  • 두개의 포인터(start, end) 가 배열의 길이(sequence.length) 가 되면 종료 한다.

투포인터 이미지

소스

public class 연속된부분수열의합 {
  @Test
  void test(){
    Assertions.assertThat(solution(new int[]{1,2,3,4,5}, 7)).isEqualTo(new int[]{2,3});
    Assertions.assertThat(solution(new int[]{1,1,1,2,3,4,5}, 5)).isEqualTo(new int[]{6,6});
    Assertions.assertThat(solution(new int[]{2,2,2,2,2}, 6)).isEqualTo(new int[]{0,2});
    Assertions.assertThat(solution(new int[]{2, 2, 2, 2, 2, 10, 10, 10, 10, 10, 10}, 30)).isEqualTo(new int[]{5,7});
  }

  private List<int[]> answers;
  public int[] solution(int[] sequence, int k) {
    int[] answer = {};

    answers = new ArrayList<>();
    findTwoPointerPairWithSum(sequence, k);

    answers.sort(Comparator.comparingInt(ints -> ints[1] - ints[0]));
    answer = answers.get(0);
    return answer;
  }

  private void findTwoPointerPairWithSum(int[] sequence, int k) {
    int start = 0;
    int end = 0;
    int currentSum = sequence[0];

    while(true){
      if(k == currentSum){
        answers.add(new int[]{start, end});
      }
      if(start == sequence.length && end == sequence.length){
        break;
      }
      if(currentSum <= k && end < sequence.length){
        end++;
        if(end < sequence.length){
          currentSum += sequence[end];
        }
      }else{
        if(start < sequence.length){
          currentSum -= sequence[start];
        }
        start++;
      }
    }
  }
}

마무리

시간 복잡도를 다시금 고민 하고 문제 풀이를 시작 하는 것을 잊지 말아야 할 것 같다는 자기 반성의 시간이였습니다.

Back to blog