연속 부분 수열 합의 개수 (자바)

김재현·2023년 12월 20일
0

알고리즘 풀이

목록 보기
61/90

문제

오답(시간초과)

    public int solution(int[] elements) {
        int answer = 0;

        // 큐에 넣는다
        Queue<Integer> intQueue = new LinkedList<>();
        for (int element : elements) {
            intQueue.add(element);
        }

        // set으로 중복 제거
        Set<Integer> intSet = new HashSet<>();
        for (int j=0;j< elements.length;j++) {
            startNext(intQueue);
            for (int i=0;i<elements.length;i++) {
                intSet.add(peekAndSum(new LinkedList<>(intQueue),i+1));
            }
        }

        answer= intSet.size();

        return answer;
    }

    // n개 꺼내고 더하기
    private int peekAndSum(Queue<Integer> queue, int n) {
        int sum=0;

        for (int i = 0; i < n; i++) {
            int a= queue.poll();
            sum+=a;
            queue.add(a);
        }

        return sum;
    }

    // 다음 배열에서 시작하기
    private Queue<Integer> startNext(Queue<Integer> intQueue) {
            int a=intQueue.poll();
            intQueue.add(a);
        return intQueue;
    }

Queue에서 꺼내는 시작 지점을 달리하면서 1~n개씩 꺼내며 더한 값을 set에 넣어주는 반복문이다.

for문이 3번이나 들어가서 겹치는 경우가 많다보니 시간초과가 나온 것으로 보인다.

정답 풀이

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int[] newElements = new int[elements.length * 2];
        
        for(int i = 0; i < elements.length; i++) {
            newElements[i] = newElements[i + elements.length] = elements[i];
        }
        
        Set<Integer> set = new HashSet<>();
        
        for(int i = 1; i <= elements.length; i++) {
            for(int j = 0; j < elements.length; j++) {
                set.add(Arrays.stream(newElements, j, j+i).sum());
            }
        }
        
        return set.size();
    }
}

사실 처음엔 int[]를 2배로 넣어버린 뒤, 더한 값들을 set에 넣으면서 풀려고 했다.

그런데 더하는 로직이 어려워서 찾아보니,
Arrays.stream(newElements, j, j+i).sum() 이런 형식으로 stream을 사용 할 수 있었다!

newElements에 대해 현재 위치 j부터 길이 i만큼의 부분 배열에 대한 스트림을 생성하는 것이다.

다른 사람 풀이

import java.util.*;

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

        for (int i=0;i<elements.length;i++) {  //i번째에서 시작
            for (int j=1;j<=elements.length;j++) {  //j번만큼 더하기
                int sum=0;
                for (int k=i;k<i+j;k++) {
                    sum+=elements[k%elements.length];
                }
                set.add(sum);
            }
        }

        return set.size();
    }
}

와! 나머지를 계산했으면 꼬리에 꼬리는 무는 원형이라는 것을 표현 할 수 있었겠구나!

나도 차라리 Queue를 안썻다면 시간초과가 안떴을까?
그래도 연습해봤으니 의미는 있다.

profile
I live in Seoul, Korea, Handsome

0개의 댓글