[C#] 프로그래머스 Lv.2 연속 부분 수열 합의 개수

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

프로그래머스

 

문제 설명
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

 

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

문제 풀이

원형 수열 문제이다. 핵심은 수열의 합을 구하는 것도 맞지만, 원 형식으로 맨 뒤의 수도 맨 앞의 수랑 연결해서 더해야 하기 때문에 주어진 수열을 늘려서 계산하는 것이 편하다.

 

수열 [7, 9, 1, 1, 4] 가 있다면, 이를 두 배로 확장하여 [7, 9, 1, 1, 4, 7, 9, 1, 1, 4 ]  로 뒤에 붙여서 같이 계산해주는 것이다. 

 

그리고 중복 값을 제거하는 것인데 C#에는 고유한 값만을 List로 저장해주는 HashSet이 있다.

 

HashSet<T> 클래스 (System.Collections.Generic)

 

이는 중복된 값이 아닌 고유한 값 만을 List로 저장해주는 역할을 한다. List와 동일하게 값을 추가할 때는 .Add() 메서드를 통해 값을 추가하고, 만약 중복된 값을 넣는다면 자동으로 걸러주게 된다.

 

HashSet<int> numbers = new HashSet<int>();

 

선언 후에 numbers.Add(1)을 연속해서 넣어도 Count에는 1만 나온다. 즉, 중복값을 허용하지 않는 것이다. 이를 활용하면 위 원형 수열 문제의 중복 값을 손쉽게 처리할 수 있다.

 

 

정답

using System;
using System.Collections.Generic;

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

        HashSet<int> lists = new HashSet<int>();


        int[] exElements = new int[elements.Length * 2];

        for(int i = 0; i < elements.Length; i++)
        {
            exElements[i] = elements[i];
            exElements[i + elements.Length] = elements[i];
        }
        
        // 1 -> 1, 7, 9, 4
        // 2 -> 16, 10, 2, 5, 11
        // 3 -> 17, 11, 6, 12 ,20
        for(int  length = 1; length <= elements.Length; length++)
        {
            for(int start = 0; start < elements.Length; start++)
            {
                int sum = 0;
                for(int i = 0; i < length; i++)
                {
                    sum += exElements[start + i];
                }
                lists.Add(sum);
            }
            
        }

        answer = lists.Count;

        return answer;
    }


    public static void Main(string[] args)
    {

        Solution s = new Solution();

        s.solution(new int[] { 7, 9, 1, 1, 4 });

        Console.WriteLine(s.solution(new int[] { 7, 9, 1, 1, 4 }));
    }
}

 

 

먼저 예시의 수열의 2배의 길이의 확장된 배열을 하나 열어주고, 여기에 수열을 재배치 해준다.

 

1. 먼저 길이만큼 더해주는 반복문을 통해 1일때 2일때 ... 배열의 길이 만큼 수열의 합을 구하는 전체 반복문을 설정한다.

2. 내부에서는 수열만큼 반복하며 초기화 하는 반복문을 넣어준다. 여기서는 sum을 반복문 시작할 때 계속 초기화 시켜줘야 하고, 안에서 계산한 값을 Add해주는 역할이다.

3. 완전 내부에는 길이만큼 더해주는 length의 길이를 받아 합을 계산하는 반복문이다. length가 2라고 가정하면 7, 9 / 9 , 1/ 1, 1 ... 이렇게 흘러가는데 start + i값을 통해 0, 1 / 1, 2 이렇게 흘러가게 된다.

 

회고

처음 접근은 2중 반복문이었으나 계산이 이상하게 돌아간다 생각하여 한번 더 반복하니 문제가 해결되었다. 헷갈리지만 정신만 차리면 풀 수 있었던 문제인 것 같다.