[JAVA/코딩테스트] 연속 부분 수열 합의 개수

문제

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

프로그래머스

 

import java.util.*;

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


        for(int i=1; i<=elements.length; i++){

            int sum = 0;
            int index = 0;
            int k = 0;

            for(int j=0; j< elements.length+i; j++){

                int m = k % elements.length;

                if(k == (elements.length-1)+i){
                    break;
                }

                if(j>=i){
                    sum += elements[m];
                    sum = sum-elements[index];
                    index++;
                }else{
                    sum += elements[m];
                }

                set.add(sum);

                k++;

            }
        }

        answer = set.size();

        return answer;
    }
}

 

처음에는 ArrayList<Integer>를 선언해서 contains 함수를 써서 리스트에 있는 숫자를 찾고자 하였지만

계속 시간초과가 떠서

HashSet을 이용하였더니 시간초과가 나지 않았다.

 

ArrayList는 contains 메소드 실행 시 처음 순차적으로 데이터 탐색을 진행하면서 값을 찾기 때문에 시간이 오래 걸린다.

 

HashSet은 비선형 구조로 순서가 없고 인덱스도 존재하지 않는다. 또한, 중복을 자동으로 제거해준다. 데이터를 있는지 확인할 때는 모든 데이터를 찾아보는 것이 아니라 데이터를 key로 순서와 상관없이 바로 확인한다. 따라서 List보다 속도가 훨씬 빠르다는 것을 알 수 있다.