[programmers] 연속 부분 수열 합의 개수

연속 부분 수열 합의 개수 문제

문제 설명

원형 수열(일반적인 수열에서 처음과 끝이 연결된 형태의 수열)의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 확인하는 문제

문제 풀이

처음에 for문으로 코드를 작성하였는데 인덱스를 계산하기가 어려워서 while문으로 바꾸는 과정에서 시간을 많이 잡아먹었다. 경우의 수를 잘 생각하고 코드를 짠다면 짧은 시간 안에 풀 수 있는 문제였던 것 같다.

이 문제에서 가장 중요하게 생각해야 할 부분은, index가 배열의 길이를 벗어난 경우이다. 배열이 7, 9, 1, 1, 4가 있고 3번째 인덱스부터 sum을 계산하고자 하는 경우 더해야할 인덱스들은 4, 7, 9, 1로 각각 4, 0, 1, 2 번째를 봐야 할 것이다. 풀이는 아래와 같다.

public int solution(int[] elements) {
    Set<Integer> set = new HashSet<>();

    int len = 0;
    int nowIndex = 0;
    int index = 0;
    int sum = 0;
    while (true) {
        // 인덱스 0부터 1씩 증가해 가면서 수를 더한다.
        // len 만큼 다 돌았다면 인덱스를 1증가하여 다음 인덱스로 넘어간다.
        // 마지막 인덱스이고, len 만큼 다 돌았다면 종료한다.
        if (len == elements.length && index == elements.length - 1) {
            break;
        }

        if (len == elements.length) {
            sum = 0;
            len = 0;
            index += 1;
            nowIndex = index;
        }

        // 인덱스가 범위를 벗어났다면 0으로 세팅해준다.
        if (nowIndex > elements.length - 1) {
            nowIndex = 0;
        }

        sum += elements[nowIndex++];
        set.add(sum);
        len += 1;
    }

    return set.size();
}

실행 결과