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

 

알고리즘 챌린지 15일 차이다. 오늘은 바로 Level2에 분류된 원형 수열문제를 풀어보겠다. 
https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

 

원형 순열의 문제를 푸는 사람들의 경우 보통 순열이 끊기지 않고 반복됨을 표현하기 위해서 배열을 두배로 확장해 이어 붙이는 경우가 있는데, 그럴 필요 없이 배열의 인덱스를 모드 연산으로 사용하면 된다. 

쉽게 말해, 길이가 5인 배열{1,2,3,4,5}이 있는데 이 배열을 논리적으로 원형으로 이어져 있다고 생각해보자. 
여기에서 5, 1, 2의 연속된 요소의 합을 구하고 싶다면, 인덱스 4, 0, 1의 합을 구해야 한다. 
배열이 연장되어 있다고 한다면, 4, 5, 6의 인덱스 합을 구하면 되는데, 5와 6은 배열의 범위를 벗어나기 때문에 에러가 날 것이다. 이때, 모든 인덱스 값을 배열의 길이만큼 모드 연산을 해주면 항상 5보다 작은 값이 나오게 되어 순환 배열을 조회할 수 있는 효과를 볼 수 있다. 
(나머지는 나누는 수보다 반드시 작다!)
논리적으로 그림을 그려보고 해당 그림을 코드로 구현하기 위한 단순한 기법(?) 정도로 생각하자. 

자 그렇다면, 각 길이별로 반복을 하면서 연속된 값을 더한 후 set에 저장만 해주면 알아서 중복값은 삭제될 테고, 마지막에 set의 size를 반환하면 되겠다. 

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        Set<Integer> hap = new HashSet<>();
        
        int len = elements.length; 
    	int size = 1;
        while(size <= len){
            for(int i=0; i<len; i++) {
                int val = 0;

                for(int j=i; j<i+size; j++) {
                    val += elements[j%len]; 
                }
                hap.add(val);
            }
        }
        return hap.size();
    }
}

 

코드 구현은 단순하다. 

하지만! 위처럼 코드를 구현하면 테스트케이스부터 시간초과가 날 것이다. ㅋㅋㅋ
직관적으로 보면 주어진 규칙대로 잘 구현된 것 같지만, 3중 반복문이 문제다. 
최악의 경우 size(1000-3) * len(1000-3) * size(1000-3) ... 대략 1000^3 정도의 연산이 발생할 수 있다. 

그렇다면 이 반복을 어떻게 최적화할 수 있을까? 
연속된 부분수열의 합을 구해야 하기 때문에 2중 반복은 피할 수 없을 것 같다. 그렇다면 가장 밖에 있는 while문, 수열의 길이별로 합을 구하는 반복은 줄일 수 있을 것 같지 않은가? 

연속된 수의 합을 구하는 것만이 중요한 것이 아니라, 결국에 합을 구하다 보면 부분수열의 구성은 다르지만 합의 값은 동일하게 중복될 수 있기 때문에 중복을 제거하는 로직을 set을 통해 간단하게 구현했다. 

이 타이밍에 해볼법한 생각은 어차피 숫자가 중복될 텐데, 굳이 수열의 길이별로 나누어서 합을 구할 필요가 있을까? 

이 생각의 시작으로 반복문을 하나 생략할 수 있다. 

elements 요소를 순회하면서, 이번 반복에서 순회하는 값하나를 기준으로
그다음 값부터 elements의 길이만큼 반복을 진행하면서 누적합을 set에 담는다. 
인덱스는 어차피 모드 연산을 하기 때문에 걱정할 필요가 없고, 기준값으로부터 배열의 길이만큼 돌기 때문에 원형 순열을 한 번 돌 수 있으며, 기준값으로부터 하나씩 누적해서 더해가기 때문에 길이도 걱정할 필요가 없다. 
결국 이 방법으로 모든 연속된 부분수열의 합을 구할 수 있는 것이다. 

아래 코드를 보면 이해가 될 것이다. 

Java

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        Set<Integer> hap = new HashSet<>();
        int len = elements.length; 

        for(int i=0; i<len; i++) {
            int val = elements[i];
            hap.add(val);
            for(int j=i+1; j<i+len; j++) {
                val += elements[j%len]; 
                hap.add(val);
            }
        }
        return hap.size();
    }
}