프로그래머스 Level2 연속 부분 수열 합의 개수

연속 부분 수열

출처: 프로그래머스

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

프로그래머스

 

문제는 위의 링크에서 확인 부탁드립니다.

간단하게 설명드리면,

수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 나올 수 있는 경우는 

길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

 

원형수열의 모든 원소가 담긴 intArray 를 주고 나올 수 있는 모든 경우의 개수를 구하면 됩니다.

 

저는 간단하게 3중 for문으로 풀었습니다.

더 빠르게 풀 수 있는 방법이 분명히 존재하겠지만 처음 보았을 때 풀었던 방법은 아래와 같습니다.

 

풀이

class Solution {
    fun solution(elements: IntArray): Int {
        var answer: Int = 0
        val arr = elements+elements
        val numSet = HashSet<Int>()
        for(i in 1..elements.size) {
            for(j in elements.indices) {
                var sum = 0
                for(k in j until j+i) {
                    sum += arr[k]
                }
                numSet.add(sum)
            }
        }
        return numSet.size
    }
}

 

3중 for문을 이용해

첫번째 반복으로 먼저 개수를 반복합니다.

개수가 1개

개수가 2개

개수가 3개

...

끝날 때까지 갑니다.

 

그리고 elements.indices 즉, elements의 원소 index를 0부터 끝까지 선형 탐색합니다.

그 안에 k가 0부터 몇 개를 더하면서 가는지 확인합니다.

 

개수가 i=1일 때, j는 0,1,2,3,4를 반복하는데

j=0일 때, k는 j=0부터 0+1(i=1)전까지 반복합니다. j는 0을 확인하여 sum에 더합니다.

그리고 k반복이 끝나고 set에 sum을 추가합니다.

j=1일 때, k는 j=1부터 1+1전까지 반복하고 j는 1을 확인하여 sum에 더합니다.

k반복이 끝나고 set에 sum을 추가하여 나올 수 있는 경우를 set에 추가합니다.

 

이렇게 3중 for문을 이용하여 개수를 먼저 정하고 그 뒤에 0 시작, 1 시작일 때 개수만큼 반복하면서 더하고 더해서 나오는 숫자가 겹치지 않게 set으로 처리하는 방법입니다. 

 

이상. 읽어주셔서 감사합니다.