[Programmers] 연속 부분 수열 합의 개수 / JAVA -> 실패

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

프로그래머스

 

---

내 코드 (주석에 분석 포함)

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        /*
        <최초 설계> 
        1. left , right 인덱스를 둔다.
        2. left ~ right 까지 길이가 0부터 elements size -1 까지 증가하는 반복문을 연다.
            2-1. left와 right가 1씩 증가하는데, left 가 right 를 넘어서면 중단되는 반복문을 연다.
            2-2. left ~ right 까지 원소의 합을 더해 '자료구조'에 저장한다
                2-2-1. 어떤 자료구조가 적합한가?
                        - 중복이 허용되지 않으면 좋다.
                        - 수정이 가능하면 좋다.
                2-2-2. HashSet 을 사용하자.
        3. HashSet 의 길이를 반환한다. 
        
        */
        
        /*
        <두번째 설계>
        1. 큐에 모든 원소를 넣는다.
        2. for(i = 0 ; i < elements.length ; i++)
            2-1. i개 만큼 꺼내서 더한 값을 HashSet에 추가한다.
            2-2. 꺼낸걸 다시 큐에 넣는다.
        3. HashSet 을 반환한다.
        
        <증명>
        3개일 때
        791 -> 14791 : 17
        147 -> 91147 : 12
        911 -> 47911 : 11
        479 -> 11479 : 20
        114 -> 79114 : 6
        
        2개일때
        79 -> 11479 : 16
        11 -> 47911 : 2
        47 -> 91147 : 11
        91 -> 14791 : 10
        14 -> 79114 : 5
    
        */
        Set<Integer> set = new HashSet<>();
        
        Queue<Integer> queue = new LinkedList<>();
        
        for(int item : elements) queue.add(item);
        
        
        for(int i=0; i<elements.length; i++){
            for(int k=0; k<elements.length; k++){
                int tempResult = 0;
                int tempPop = 0;
                for(int j=0; j<=i; j++){
                    tempPop = queue.remove();
                    tempResult += tempPop;
                    queue.add(tempPop);
                }
                set.add(tempResult);
            }
        }
        return set.size();
    }
}

경험과 지식이 부족하니까 근본없이 내 마음대로 푸는 것 같다.

아무도 이렇게 푸는 사람이 없을 뿐더러 풀이에 급급하느라 Time, Space 모두 고려하지 못했다.

시간도 한시간 정도 소요되었다.

 

너무 슬프지만.. 다른 분들의 풀이를 보며 배워보자. 🥲🥲🥲

---

다른 분의 풀이

https://velog.io/@jp-share/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%97%B0%EC%86%8D-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%95%A9%EC%9D%98-%EA%B0%9C%EC%88%98-Java

[코딩테스트] 프로그래머스 - 연속 부분 수열 합의 개수 (Java)

 

 

해당문제는 Set을 활용한 문제입니다.
풀이방법
1. 원형수열로 끝자리에서 처음자리로 다시이어지는 경우로 인해 배열을 2배 추가로 늘리기
2. 합계 중복 미허용 set 변수선언
3. 순차 인덱스에서 n번까지 실행을 더한값 set 저장
4. set 크기 반환

코드

import java.util.*;
import java.util.stream.*;

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();
    }
}

---

비교 분석

일단 자료구조 선택에서 중복을 허용하지 않는 Set을 설정한 점은 잘했다.

그리고 원형수열은 기존 배열을 2배로 늘려서 처리할 수 있음을 배웠다.

바로 이 점이 첫번째 설계에서 중지했던 가장 중요한 요소였다.

IndexOutOfBounds 를 예상하며 어떻게 인덱스를 처리할 지 감이 오지 않았었기 때문이다.

이외에 Arrays.stream() 을 사용하는 방법에 대해 배울 수 있었다.