프로그래머스 - 연속 부분 수열 합의 개수

홍성진·2023년 5월 2일
0

프로그래머스 - 연속 부분 수열 합의 개수

주어진 원순열에서 부분수열의 합을 구합니다. 이 때 나올 수 있는 합의 개수를 구하는 문제입니다. 중복없이 개수를 구해야 하기 때문에 모든 합들을 set에 넣자는 아이디어를 떠올렸습니다. 또한 연속한 수열의 합이기 때문에 누적합을 이용하면 반복적인 계산을 생략할 수 있습니다.

prefixes의 각 i번째 row에 elements[i]로 시작하는 수열의 누적합들을 기록합니다.
prefixes[i][j]i항부터 시작하는 길이가 j인 부분수열의 합이 됩니다.

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int len = elements.length;
        int[][] prefixes = new int[len][len + 1];
        HashSet<Integer> set = new HashSet<>();
        
        for (int i = 0; i < len; i++) {
            int prev = 0;
            
            for (int j = 0; j < len; j++) {
                prefixes[i][j + 1] = prev + elements[(i + j) % len];
                prev = prefixes[i][j + 1];
            }
        }
                    
        for (int i = 0; i < len; i++) {
            for (int j = 1; j <= len; j++) {
                set.add(prefixes[i][j]); // 굳이?
            }
        }    
        
        return set.size();
    }
}

그런데 두번째 반복문을 잘 보면 작업이 set.add(prefixes[i][j]) 뿐인데, 굳이 prefixes라는 array를 만들지 않더라도 바로 set에 넣을 수 있습니다.

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int len = elements.length;
        HashSet<Integer> set = new HashSet<>();
        
        for (int i = 0; i < len; i++) {
            int prev = 0;
            
            for (int j = 0; j < len; j++) {
                prev = prev + elements[(i + j) % len];
                set.add(prev + elements[(i + j) % len]);
            }
        }
        
        return set.size();
    }
}

0개의 댓글