TIL 22일차 (연속 부분 수열 합의 개수 - Kotlin)

코드카타

 

연속 부분 수열 합의 개수

 

문제

 

주어진 원형 배열의 모든 부분 배열 합을 구하는 문제이다.

 

 

입출력 예시

 

2중 for문을 돌려 모든 부분 수열의 합을 구하고 중복되는 값을 제거해줘야 한다.

 

 

풀이

class Solution {
    fun solution(elements: IntArray): Int {
    	// 부분배열 합의 중복을 제거하기 위해 가변형 set 선언
        val set = mutableSetOf<Int>()
		
        // 이중 for문을 통한 부분 배열 생성
        for (i in 1..elements.size) 
            for (j in elements.indices) { 
                var sum = 0  
                // 부분배열의 합 계산
                for (k in j until i + j) {
                    // 원형 배열의 특성을 고려하여 인덱스 계산
                    sum += elements[k % elements.size] 
                }
                set.add(sum) // 계산된 합을 set에 추가
            }
        }
        // set의 크기(중복되지 않는 모든 부분 배열 합의 개수)를 반환
        return set.size
    }
}

3중 for문을 통해 주어진 원형배열에서 모든 부분배열의 합을 구한 뒤

중복을 제거한 부분배열 합의 수를 반환하는 문제였다.

 

 

부분 배열 생성 로직

// 어떤식으로 부분배열이 생성되는지 확인하기 위해서
// 길이가 n일 때마다 생성되는 모든 부분배열을 출력하는 로직을 짰다.

fun main() {
    val elements = intArrayOf(7, 9, 1, 1, 4)
	
    for (i in 1..elements.size) {
        print("길이 $i: ")
        for (j in elements.indices) {
            var res = mutableListOf<Int>()
            for (k in j until i + j) {
                res.add(elements[k % elements.size])
            }
            print("$res ")
        }
        println()
    }
}

i는 (1 ~ elements 배열 크기)의 값을 가지고

j는 elements의 인덱스 범위를 값으로 가진다.

 

해당구문에서 k는 j ~ (i + j -1) 의 범위를 가지는데

이는 부분 배열을 구성하는 요소의 인덱스에 해당한다.

 

 

// 위 main함수 실행 결과

길이 1: [7] [9] [1] [1] [4] 
길이 2: [7, 9] [9, 1] [1, 1] [1, 4] [4, 7] 
길이 3: [7, 9, 1] [9, 1, 1] [1, 1, 4] [1, 4, 7] [4, 7, 9] 
길이 4: [7, 9, 1, 1] [9, 1, 1, 4] [1, 1, 4, 7] [1, 4, 7, 9] [4, 7, 9, 1] 
길이 5: [7, 9, 1, 1, 4] [9, 1, 1, 4, 7] [1, 1, 4, 7, 9] [1, 4, 7, 9, 1] [4, 7, 9, 1, 1]

해당 3중 for문은 주어진 배열의 모든 가능한 부분 배열을 구하기 위해

배열크기가 n이라고 할 때, n^2번 반복해서 모든 가능한 부분 배열의 합을 구한다.

 

 

원형 배열의 특성 고려

sum += elements[k % elements.size]

원형 배열은 배열의 끝에 도달했을 때 다시 배열의 처음으로 돌아간다.

배열의 경계를 넘어가는 경우, 즉 k가 주어진 배열크기보다 큰 값을 가진 경우를 고려한다.

 

 

회고

2중 for문을 사용하는 로직은 머릿속으로 구현할만한데

3중 for문부터는 이해하기도 어려운 느낌이다.

 

수열의 규칙성을 찾아내는 dp문제인 줄 알았는데 

3중 for문을 통해 모든 부분배열의 합을 구하는 문제였다.

 

아직 문제풀이 경험이 부족함을 느꼈기에 더 많은 문제를 풀어봐야겠다.