[프로그래머스] 비밀 코드 해독 (Kotlin)

카테고리

DFS

나만의 카테고리

DFS

문제 링크

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

---

🧠 요점

• 전체 조합을 생성한 후 조건에 맞는지 검증하는 방식
• 시간 초과를 막기 위해 조건 필터링을 효율적으로 구현
• DFS로 조합을 생성하고, 조건 검증은 intersect와 any로 간결하게 처리

---

📚 참고 지식

• DFS (조합 생성)
• Kotlin intersect()
• Kotlin any { ... } 를 활용한 조건 조기 종료

---

💻 풀이 (Kotlin)

[기존 풀이 코드]
class Solution {
    var fullCombination: List<List<Int>> = emptyList()
    
    fun solution(n: Int, q: Array<IntArray>, ans: IntArray): Int {
        fullCombination = combination((1..n).toList())
        
        val qAnsPairs = q.mapIndexed { idx, eachQ ->
            Pair(eachQ.toList(), ans[idx])
        }

        println("테스트 사이즈: " + listOf(1,2,3,4,5).intersect(listOf(7,8,1,2,3)).size)
        
        return filteredCount(qAnsPairs)
    }
    
    fun combination(list: List<Int>): List<List<Int>> {
        val result = mutableListOf<List<Int>>()

        fun combine(start: Int, current: List<Int>) {
            if (current.size == 5) {
                result.add(current)
                return
            }

            for (i in start until list.size) {
                combine(i + 1, current + list[i])
            }
        }

        combine(0, emptyList())
        return result
    }
    
    fun filteredCount(pairs: List<Pair<List<Int>, Int>>): Int {
        return fullCombination.filter { combination ->
            pairs.forEach { pair ->
                if (combination.intersect(pair.first).size != pair.second) return@filter false
            }

            return@filter true
        }.size
    }
}


[GPT 개선 코드]
class Solution {
    fun solution(n: Int, q: Array<IntArray>, ans: IntArray): Int {
        val allCombinations = generateCombinations((1..n).toList(), 5)
        val queries = q.map { it.toList() }.zip(ans.toList())

        return allCombinations.count { candidate ->
            isCandidateValid(candidate, queries)
        }
    }

    private fun generateCombinations(elements: List<Int>, size: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()

        fun backtrack(start: Int, current: List<Int>) {
            if (current.size == size) {
                result.add(current)
                return
            }

            for (i in start until elements.size) {
                backtrack(i + 1, current + elements[i])
            }
        }

        backtrack(0, emptyList())
        return result
    }

    private fun isCandidateValid(candidate: List<Int>, queries: List<Pair<List<Int>, Int>>): Boolean {
        return !queries.any { (query, expectedMatchCount) ->
            candidate.intersect(query.toSet()).size != expectedMatchCount
        }
    }
}

 

🧩 핵심 포인트

• DFS 방식으로 전체 조합을 만드는 방식
• any { ... }를 사용해 조건 불충족 시 빠르게 제외

---

💬 회고

이 문제의 핵심은 전체 조합을 만들어야 하냐 마냐를 빠르게 판단 하고 DFS 방식으로 빠르게 접근하는 것이 포인트 인 것 같습니다.

역시나 GPT가 훨씬 깔끔하게 풀기는 합니다... 그래도 연습은 필요하네요.

• kotlin 함수를 더 마스터 하는 것
• 이름을 더 깔끔하게 짓자