2024.06.17 TIL 코트카타 85번(연속 부분 수열 합의 개수)

    fun solution(elements: IntArray): Int {
        val sumSet = mutableSetOf<Int>()
        val sumElements = mutableListOf<Int>()
        val rotatingElements = mutableListOf<Int>()

        for (element in elements) {
            sumSet.add(element)
            sumElements.add(element)
            rotatingElements.add(element)
        }

        var numRotate = 2
        while (numRotate < elements.size) {
            rotatingElements.add(rotatingElements[0])
            rotatingElements.removeFirst()
            for (sumIndex in sumElements.indices) {
                val sumNumber = sumElements[sumIndex] + rotatingElements[sumIndex]
                sumElements[sumIndex] = sumNumber
                sumSet.add(sumNumber)
            }
            numRotate++
        }

        rotatingElements.add(rotatingElements[0])
        rotatingElements.removeFirst()
        sumSet.add(sumElements[0] + rotatingElements[0])

        return sumSet.size
    }

 

풀이과정

1. elements의 원소를 sumSet에 전부 넣는다.(길이가 1인 부분수열의 합)

2. 합을 구하는 list(sumElements)에 한칸씩 왼쪽으로 element를 이동하는 list(rotatingElements)를 한 칸씩 이동하면서 합을 계속 누적한다.

3. 각각구해진 합은 set에 넣는다.

4. set의 size를 반환한다.

 

포인트

- sumElements에 rotatingElements를 한칸씩 왼쪽으로 밀며 더해주면 해당 인덱스를 기준으로 오른쪽 인덱스의 값(연속으로 이어지는 수)를 한 칸씩 더하는 것이 되기 때문에 연속된 부분 수열의 합을 구할 수 있다.