[Algorithm] Programmers_연속 부분 수열 합의 개수

💡 Programmers Lv2. 연속 부분 수열 합의 개수:

Set을 활용하여 원형 배열의 부분 수열 합 구하기

🌱 코드 in Java

알고리즘: BruteForce?

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> answer = new HashSet<>();
        int len = elemnets.length;
        
        for (int i = 0; i < len; i++) {
        	int tmp = 0;
            for (int j = 0; j < len; j++) {
            	tmp += elements[(i + j) % len]; // 나머지 연산을 통한 원형 배열 순회
                answer.add(tmp); // 누적합
            }
        }
        return answer.size();
   }
}

이번 문제는 부분 수열의 합에서 중복된 값을 제거하는 것이 중요 포인트로, Set 자료형을 사용하였다. 원형 배열은 내가 사랑하는 자료구조여서 나머지 연산을 통한 접근법이 바로 떠올랐다. 그런데 다른 풀이들을 찾아보니 같은 배열을 2개 붙여서 진행하는 방식도 많아 보였다.

아무튼, 나는 처음에는

        for (int i = 0; i < len; i++) {
            for (int j = 1; j <= len; j++) {
                int tmp = 0;
                int l = i;
                for (int k = 1; k <= j; k++) {
                    tmp += elements[l % len];
                    l++;
                }
                answer.add(tmp);
            }
      	}

이런 식으로 삼중 포문을 돌렸었다. 각각의 인덱스에 대해서 자기 자신, 자기 자신 + 1, 자기 자신 + 2 ... 자기 자신 + 마지막 인덱스 이런식으로 돌리고 싶었던 거였는데, 아무래도 삼중 포문을 돌릴 일인가 싶어서 챗쥐피티의 힘을 빌렸더니 위와 같이 이중 포문으로 바꾸어주었다.

왜 난 이런 생각이 바로 안 떠오를까? 다음부턴 더 생각해보기를.

class Solution {
    public int solution(int[] elements) {
        Set<Integer> answer = new HashSet<>();
        int len = elements.length;

        for (int i = 0; i < len; i++) {
            final int start = i;
            answer.add(IntStream.range(0, len)
                    .map(j -> elements[(start + j) % len])
                    .sum());
        }

        return answer.size();
    }
}

이렇게 스트림처리도 가능하다. 스트림.. 언제 공부하냐 ㅠㅠ

🧠 기억하자

1. IntStream.range(i, j)

• i부터 j-1까지

2. map

• 스트림의 각 요소에 함수를 적용하여 새로운 값을 생성하는 역할을 함
• IntStream의 각 요소 j에 대해 elemens[(start + j) % len]을
• 새로운 스트림을 생성함

3. sum

• 스트림의 모든 요소를 더한 결과를 반환 -> answer.add의 결과값이 됨.

2. final

• 람다 표현식 내에서 외부 지역 변수를 사용할 때 해당 변수는 final 이어야 한다고 한다. final 키워드를 사용하지 않아도 되기는 하지만, 명시적으로 사용하는 것이 좋은 프로그래밍!