[C#] 연속 부분 수열 합의 개수

프로그래머스 문제

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

풀이 후기

1. 분석

하라는 대로 3중 배열 돌리면 푼어진다. for(모든 칸) -> for(1개~n개) -> for(더해야 하는 칸)

2. 실행 결과

3. 코드

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    List<int> answer = new List<int>();

    public void CalcCircle(int n, int[] elements, int len){
        for(int x = 0; x < len; x++){
            int sum = 0;
            for(int y = 0; y < n; y++){
                var index = (x + y) % len;
                sum += elements[index];
            }
            answer.Add(sum);
        }
    }

    public int solution(int[] elements) {
        int circleLen = elements.Length;

        for(int i = 1; i <= circleLen; i++){
            CalcCircle(i, elements, circleLen);
        }

        return answer.Distinct().Count();
    }
}

1. 진짜 분석

근데 이렇게 풀면 재미없음. 조금만 더 분석해보면 중복 계산이 된다는 걸 볼 수 있다. 예를 들어 3개의 값을 더하는 건, 2개의 값 + 1개의 값이라는 분석이 나온다.

1번 + 2번 = [1번 + 2번] = A
1번 + 2번 + 3번 = [1번 + 2번 + 3번] or [A + 3번]

어캐 표현해야 하는지 몰라서 대충 표현함. 그니까 길이5의 개수 만큼을 더할 때, 이미 길이1, 길이2, 길이3... 등등도 계산하게 되는 것. 해결 방법은 마지막 길이만 계산하는 동시에 List에 집어넣으면 된다. HashSet쓰면 Distinct를 굳이 안 써도 되기에 이득은 덤.

2. 실행 결과

많이 줄었다.

3. 코드

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    private static HashSet<int> answer = new HashSet<int>();

    public class Item{
        public int index;
        public static int[] elements;
        public static int len;
        
        public Item(int i){
            index = i;
        }
        
        public static void SetElements(int[] e){
            elements = e;
            len = e.Length;
        }
        
        public void Calc(){
            // 1~n-1개
            int sum = 0;
            for(int i = 0; i < len - 1; i++){
                var newIndex = (index + i) % len;
                sum += elements[newIndex];
                answer.Add(sum);
            }
            
            // 마지막은 계산 필요 없음
        }
    }
    
    
    public int solution(int[] elements) {
        int circleLen = elements.Length;
        Item.SetElements(elements);
        
        for(int i = 0; i < circleLen; i++){
            new Item(i).Calc();
        }

        return answer.Count + 1;
    }
}

그리고 별로 안 중요하지만 배열의 길이와 같은 마지막 길이의 계산 결과는 요소에 음숫값이 없어서 무조건 1개가 나온다. 그러므로 계산 안 하고 정답 개수에+1 해서 날로 먹기 가능.