[Level 1] 소수 만들기 - combination(조합)

[내배캠 - 오늘의 문제]

문제의 point1. n개의 요소중 3개를 뽑는 로직

// Time: 5.99 ms, Memory: 61.2 MB
class Solution {
    val combinationNumbers = mutableListOf<Int>()
    val combinationGroup = mutableListOf<List<Int>>()
    lateinit var numbersBackup: IntArray

    fun solution(nums: IntArray): Int {
        // 1. 주어진 배열에서 3개씩 뽑는다.
        numbersBackup = nums
        combination(0, 0)

        // 2. 1차원 배열끼리 합한다. / 그 합한 수가 소수인지 판별한다.
        return combinationGroup.map { numbers -> numbers.sum() }
            .filter { sum -> isNotDecimal(sum) }
            .count()
    }

    fun combination(currentIndex: Int, depth: Int) {
        if (depth == goalDepth) {
            // println(combinationNumbers)
            combinationGroup.add(combinationNumbers.toList())
            return
        }

        for (i in currentIndex until numbersBackup.size) {
            combinationNumbers.add(numbersBackup[i])
            combination(i + 1, depth + 1)
            combinationNumbers.removeAt(combinationNumbers.lastIndex)
        }
    }

    fun isNotDecimal(num: Int): Boolean {
        val roofIndex = Math.sqrt(num.toDouble()).toInt()
        for (i in 2..roofIndex) {
            if (num % i == 0) {
                return false
            }
        }
        return true
    }

    companion object {
        val goalDepth = 3
    }
}

 

조합 관련 로직은 재귀호출 말고도 가능하지만, 평소 재귀호출을 어려워하던 나여서 이번 기회에 추가로 학습해보려 한다. 

 

kotlin 조합 관련 블로그를 참고하여 combination을 이해한 뒤, 직접 구현하다가 막혀서 제일 마지막 라인인 아래 코드를 복붙해서 사용했다. 어느정도 이해는 됐지만, 직접구현(combinationNumbers는 항상 3개의 요소만 존재하기 때문에 MutableList타입이 아닌 IntArray 타입으로 초기화해서 쓰고싶었다)에 어려움이 있었고 설명할 정도의 레벨이 아닌 것 같아

conbinationNumbers.removeAt(combinationNumbers.lastIndex)

 

오늘은 아래 메서드를 전체적으로 손버깅 해보려 한다.

fun main() {
	combination(0, 0)
}

class Solution {
	val combinationNumbers = mutableListOf<Int>()
    val numbers = intArrayOf(1, 2, 3, 4)

    fun combination(currentIndex: Int, depth: Int) {
        if (depth == goalDepth) {
        	// [1, 2, 3] -> [1, 2, 4] -> [1, 3, 4] -> [2, 3, 4]
            println(combinationNumbers) 
            combinationGroup.add(combinationNumbers.toList())
            return
        }

        for (i in currentIndex until numbers.size) {
            combinationNumbers.add(numbers[i])
            combination(i + 1, depth + 1)
            combinationNumbers.removeAt(combinationNumbers.lastIndex)
        }
    }
    
    companion object {
        val goalDepth = 3
    }
}

 

규칙 : combination() as cobi / combinationNumber as cn

 

depth가 헷갈릴 수 있으니 notion의 toggle 기능을 활용했다.

https://humorous-ptarmigan-c7f.notion.site/Kotlin-Combination-6131883c52524d75864aa61ca6bc0bfe?pvs=4

Kotlin Combination(조합) | Notion

 

아래는 손버깅한 결과인데, 보기가 어려워서 토글을 적절히 사용해서 위의 노션에 정리했다.

마음 같아선 [1, 2, 3, 4, 5]의 예시로 해보고 싶었지만, 어떻게 돌아가는 로직인지는 충분히 이해했기에 (그렇지만, 아직 텍스트로 설명할 수 있는 레벨은 아닌 것 같다,,, 그림은 가능할 지도 ㅎㅎ,,) 손버깅은 이쯤한다.

 

그럼 전에 하고 싶었던 IntArray로 구현해보자 (수정된 코드는 아래 첨부)

https://github.com/rlaxodud214/CodingTest_Kotlin/commit/4dbf4f6b1c42a518a7610783f57eb7086b455368

[level 1] Title: 소수 만들기, Time: 25.06 ms, Memory: 63.1 MB -BaekjoonHub · rlaxodud214/CodingTest_Kotlin@4dbf4f6

 

nextInputIndex은 데이터를 담을 다음 공간이므로

- 데이터를 넣은 후엔 ++을 

- 데이터를 삭제할 때는 --로 접근해서 0으로 초기화 하는 코드로 수정했다.

 

시간이 단축될 줄 알았지만, 4배 가량 증가했다,,, 이유는 뭘까,,, ㅎㅎㅎㅎ

감사하게도 동기분이 코드 리뷰를 해주셨고, 이유를 찾을 수 있었다.

 

1. mutableListOf는 인라인 함수이고, Array는 아니다.

2. 추가 작성 예정

combinationGroup.add(listOf(*combinationNumbers))

 

 

이제 과제에 집중하자. 재밌는 프로젝트가 생겨 기쁘게 임하는 중이다.

앞으로 combination 코드를 까먹을 일은 없을 것 같다!!

 

손버깅 로그(아래 클릭)

• 1-0. cobi (index = 0, depth = 0) call
  • if = false
  • for (i in 0..3) {
    • i = 0
      • cn.add(numbers[0] == 1) -> cn : [1]
      • 2-0. cobi (index = 1, depth = 1) call
        • if = false
        • for (i in 1..3) {
          • i = 1
          • cn.add(2) -> cn : [1, 2] 3-0. cobi (index = 2, depth = 2) call if = false for (i in 2..3) { i = 2 -------- i == 2 ------------------------------------- cn.add(3) -> cn : [1, 2, 3] 4-0. cobi (index = 3, depth = 3) call if = true -> [1, 2, 3] 출력, 백업, return cn.removeAt(2) -> [1, 2] -------- i == 3 ------------------------------------- cn.add(4) -> cn : [1, 2, 4] 4-1. cobi (index = 4, depth = 3) call if = true -> [1, 2, 4] 출력, 백업, return cn.removeAt(2) -> [1, 2] } cn.removeAt(1) -> [1]
          • i = 2
          • cn.add(numbers[2] = 3) -> cn : [1, 3] 3-1. cobi (index = 3, depth = 2) call if = false for (i in 3..3) { i = 2 -------- i == 3 ------------------------------------- cn.add(numbers[3] = 4) -> cn : [1, 3, 4] 4-0. cobi (index = 4, depth = 3) call if = true -> [1, 3, 4] 출력, 백업, return cn.removeAt(2) -> [1, 3] } cn.removeAt(1) -> [1]
          • i = 3
          • cn.add(numbers[3] = 4) -> cn : [1, 4] 3-2. cobi (index = 4, depth = 2) call if = false for (i in 4..3) {} -> 실행 x cn.removeAt(1) -> cn : [1]
      • cn.removeAt(0) -> cn : [ ]
    • i = 1
      • cn.add(numbers[1] == 1) -> cn : [2]
      • 2-1. cobi (index = 2, depth = 1) call
        • if = false
        • for (i in 2..3)
          • i = 2
          • cn.add(2) -> cn : [2, 3] 3-0. cobi (index = 3, depth = 2) call if = false for (i in 3..3) { i = 3 -------- i == 3 ------------------------------------- cn.add(3) -> cn : [2, 3, 4] 4-0. cobi (index = 4, depth = 3) call if = true -> [2, 3, 4] 출력, 백업, return cn.removeAt(2) -> [2, 3] } cn.removeAt(1) -> [2]
          • i = 3
          • cn.add(3) -> cn : [2, 4] 3-1. cobi (index = 4, depth = 2) call if = false for (i in 4..3) {} -> 실행 x cn.removeAt(1) -> [2]
      • cn.removeAt(0) -> cn : [ ]
    • i = 2
      • cn.add(numbers[2] == 3) -> cn : [3]
      • 2-2. cobi (index = 3, depth = 1) call
        • if = false
        • for (i in 3..3)
          • i = 3
          • cn.add(3) -> cn : [3, 4] 3-0. cobi (index = 4, depth = 2) call if = false for (i in 4..3) {} -> 실행 x cn.removeAt(1) -> cn : [3]
      • cn.removeAt(0) -> cn : [ ]
    • i = 3
      • cn.add(numbers[3] == 4) -> cn : [4]
      • 2-3. cobi (index = 4, depth = 1) call
        • if = false
        • for (i in 4..3) -> 실행 x
      • cn.removeAt(0) -> cn : [ ]