[프로그래머스 / 연습문제 / 자바(JAVA)] 연속 부분 수열 합의 개수

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

 

▼ ▼ ▼

정답 풀이로 바로 가기

▲ ▲ ▲

 

풀이 1

로직

1. int i 배열에서 더하기를 시작할 수의 인덱스
2. int j 더하는 숫자의 개수
   • 0부터 elements.length 미만까지 늘어난다.
3. int k 더하는 숫자의 인덱스
   • i 부터 i+j 까지 늘어난다.
4. 만약 k가 elements.length 이상이 된다면, k에서 elements.length를 빼준다.
5. 이들을 이용한 반복문으로 구한 합계를 HashSet에 저장해준다.
   • HashSet은 중복을 허용하지 않기 때문이다.
6. HashSet의 size를 return한다.

조금 더 간소화 할 수 있을 듯 한데, 일단 이렇게 시도해본 후 간소화해보자.

 

코드

import java.util.*;

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

        for(int i=0; i<elements.length; i++) {
            for(int j=0; j<elements.length; j++) {
                for(int k=i; k<=i+j; k++) {
                    if(k>=elements.length) {
                        sum += elements[k-elements.length];
                        // System.out.print(" + " + elements[k-elements.length]);
                    } else {
                        sum += elements[k];
                        // System.out.print(" + " + elements[k]);
                    }
                }
                // System.out.println(" = " + sum);
                set.add(sum);
                sum = 0;
            }
        }

        return set.size();
    }
}

 

채점 결과

정확성  테스트
테스트 1 〉    통과 (0.06ms, 92.6MB)
테스트 2 〉    통과 (22.35ms, 78.7MB)
테스트 3 〉    통과 (46.55ms, 84.4MB)
테스트 4 〉    통과 (77.67ms, 87.8MB)
테스트 5 〉    통과 (149.08ms, 88.8MB)
테스트 6 〉    통과 (264.88ms, 114MB)
테스트 7 〉    통과 (362.97ms, 112MB)
테스트 8 〉    통과 (626.06ms, 123MB)
테스트 9 〉    통과 (850.93ms, 126MB)
테스트 10 〉    통과 (1286.24ms, 115MB)
테스트 11 〉    통과 (226.01ms, 106MB)
테스트 12 〉    통과 (300.57ms, 106MB)
테스트 13 〉    통과 (326.17ms, 121MB)
테스트 14 〉    통과 (466.31ms, 122MB)
테스트 15 〉    통과 (543.73ms, 127MB)
테스트 16 〉    통과 (589.61ms, 131MB)
테스트 17 〉    통과 (682.81ms, 113MB)
테스트 18 〉    통과 (780.44ms, 111MB)
테스트 19 〉    통과 (962.62ms, 127MB)
테스트 20 〉    통과 (1034.27ms, 121MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

음... 좋은 풀이는 아닌 듯 하다.

 

풀이 2 (개선하기)

 

로직

조금 더 간소화 해보자.

1. elements[0] 부터,
   • 수 1개의 합 (elements[0]) => HashSet에 add
   • 수 2개의 합 (elements[0] + elements[1]) => HashSet에 add
   • 수 3개의 합 (elements[0] + elements[1] + elements[2]) => HashSet에 add
   • ...
   • 수 elements.length개의 합 => HashSet에 add
2. elements[1] 부터, 다시 반복
   • 수 1개의 합 (elements[1]) => HashSet에 add
   • 수 2개의 합 (elements[1] + elements[2]) => HashSet에 add
   • 수 3개의 합 (elements[1] + elements[2] + elements[3]) => HashSet에 add
   • ...
   • 수 elements.length개의 합
     (elements[1] + elements[2] + ... + elements[elements.length-1] + elements[0] ) => HashSet에 add
3. 이를 elements[elements.length-1] 까지 다시 반복
   • 원형순열이기에 자연히 인덱스는 elements.length-1를 넘어가게 된다.
   • 그러므로 수의 개수를 담당하는 int j를 elements.length로 나눈 나머지를 인덱스로 활용한다.
4. HashSet의 size를 return한다.

 

코드

import java.util.*;

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

        for(int i=0; i<elements.length; i++) {
            for(int j=i; j<i+elements.length; j++) {
                sum += elements[j%elements.length];
                set.add(sum);
            }
            sum = 0;
        }

        return set.size();
    }
}

 

채점 결과

정확성  테스트
테스트 1 〉    통과 (0.13ms, 73.9MB)
테스트 2 〉    통과 (10.72ms, 82.2MB)
테스트 3 〉    통과 (25.93ms, 97.7MB)
테스트 4 〉    통과 (30.89ms, 93.4MB)
테스트 5 〉    통과 (60.99ms, 95.2MB)
테스트 6 〉    통과 (119.72ms, 95.5MB)
테스트 7 〉    통과 (105.62ms, 114MB)
테스트 8 〉    통과 (161.24ms, 118MB)
테스트 9 〉    통과 (254.56ms, 117MB)
테스트 10 〉    통과 (267.26ms, 122MB)
테스트 11 〉    통과 (94.44ms, 98.1MB)
테스트 12 〉    통과 (122.61ms, 90.2MB)
테스트 13 〉    통과 (126.34ms, 99MB)
테스트 14 〉    통과 (103.66ms, 114MB)
테스트 15 〉    통과 (201.71ms, 128MB)
테스트 16 〉    통과 (162.34ms, 110MB)
테스트 17 〉    통과 (267.38ms, 115MB)
테스트 18 〉    통과 (176.75ms, 111MB)
테스트 19 〉    통과 (301.93ms, 122MB)
테스트 20 〉    통과 (325.91ms, 114MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0