[pg] 프로그래머스 연속된 부분 수열의 합

1. 문제정의

 문제에서 비내림차순으로 정렬된 수열의 배열과 k값이 주어지는데, 배열 안의 연속된 값의 합이 부분수열의 합이 k가 되는 가장 작은 인덱스 범위를 구하는 것이다.

예시) 배열 : [1,2,3,4,5]  k: 5 일때  연속된 수열의 부분수열의 합으로 5가 되는 경우의 수는 [2,3], 그리고 [5] 이다. 이때 5의 인덱스는 4이므로 시작인덱스와 끝인덱스인 [4,4]가 리턴되면 된다. 

2. 내가 한 시도

 일단 시작인덱스와 끝인덱스 2개의 값을 관리하는 것이 귀찮아서 sum 값과 queue를 이용해서 풀기로 했다.

1. 순차적으로 큐에 값을 넣으면서 k값을 체크.

2. sum값과 k값이 같아지면 인덱스의 시작과 끝 값을 저장[큐에서 peek, 현재 위치 index]

3. sum값보다 k값이 크면 k 보다 작아질 때까지 dequeue

4. 다시 1부터 반복하는 식으로 코드 로직을 작성하고자 생각했다.

3. 코드

import java.util.LinkedList;
import java.util.Queue;

/**
 * <p>
 * 프로그래머스 LV2
 * 연속된 부분 수열의 합
 * 접근 방법: 2개의 인덱스 정보를 가지고 조작하는 것이 필요하지만 큐를 이용해서 하나의 인덱스로 해결
 */
public class Solution {

    public static void main(String[] args) {
        int[] solution = solution(new int[]{1, 1, 1, 2, 3, 4, 5}, 5);
        System.out.println(solution[0]);
        System.out.println(solution[1]);
    }

    public static int[] solution(int[] sequence, int k) {
        /*
         * 나중에 리턴할 정답. 정답은 0~k보다 무조건 범위가 좁음
         */
        int[] answer = {0, k};

        /*
         * 인덱스와 숫자정보를 가지고 있는 Number 객체 큐
         */
        Queue<Number> queue = new LinkedList<>();
        /*
         * 합계를 관리
         */
        int sum = 0;

        /*
         * 순차적으로 for문을 돌면서 Number객체를 큐에 넣고, sum값보다 k값이 적으면 sum값보다 같거나 작아질때까지 dequeue.
         * sum 값과 k값이 같다면 범위를 구해서 정답배열에 넣어준다. (이전 범위보다 적을경우에만)
         */
        for (int index = 0; index < sequence.length; index++) {
            sum += sequence[index];
            queue.offer(new Number(index, sequence[index]));

            while (sum > k) {
                Number poll = queue.poll();
                sum -= poll.getNumber();
            }

            if (sum == k) {
                Number peek = queue.peek();
                int range = index - peek.getIndex();
                if (range < answer[1] - answer[0]) {
                    answer[0] = peek.getIndex();
                    answer[1] = index;
                }

            }
        }
        return answer;
    }

    static class Number {
        private int index;
        private int number;

        public Number(int index, int number) {
            this.index = index;
            this.number = number;
        }

        public int getIndex() {
            return index;
        }

        public int getNumber() {
            return number;
        }
    }
}

4. 회고

 아래쪽 로직을 짤 때 조금 헷갈리는 부분이 있었지만 디버깅을 통해 잘 해결했다. 역시 2개의 인덱스를 컨트롤 하는 문제는 큐를 이용하면 편하게 문제를 풀 수 있다.

 

참조

https://school.programmers.co.kr/learn/courses/30/lessons/178870