문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/388352?language=kotlin
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
| 당신은 비밀 조직의 보안 시스템을 뚫고 중요한 정보를 해독해야 합니다. 시스템은 1부터 n까지의 서로 다른 정수 5개가 오름차순으로 정렬된 비밀 코드를 가지고 있으며, 당신은 이 비밀 코드를 맞혀야 합니다. 당신은 비밀 코드를 알아내기 위해 암호 분석 도구를 사용하며, m번의 시도를 할 수 있습니다. 각 시도마다 서로 다른 5개의 정수를 입력하면, 시스템은 그 중 몇 개가 비밀 코드에 포함되어 있는지 알려줍니다.
|
📌 목표 : 1부터 n까지의 정수 중 5개를 골라 만든 조합이, 주어진 여러 번의 시도(q 배열)에서 시스템의 응답(ans 배열)과 일치하는지 확인하고, 가능한 모든 조합의 개수를 구합니다.
• 백트래킹(Backtracking) 기법:
1부터 n까지의 숫자 중 5개를 선택하는 모든 조합을 생성합니다.
• 각 조합에 대한 조건 검사:
각 조합이 주어진 시도마다 해당 시도의 숫자와 몇 개가 겹치는지 계산한 후, 그 값이 ans 배열에 기록된 값과 동일한지 확인합니다.
• Set을 이용한 효율성:
시도에 사용된 숫자들을 Set으로 변환하여, 조합과의 교집합을 쉽게 구할 수 있게 합니다.
✅코드
fun solution(n: Int, q: Array<IntArray>, ans: IntArray): Int {
// 각 시도의 숫자 배열을 Set으로 변환하여 빠른 멤버십 검사를 수행합니다.
val queries = q.map { it.toSet() }
var count = 0
// 백트래킹 함수: start부터 n까지 선택하여 current에 담습니다.
fun backtrack(start: Int, current: MutableList<Int>) {
if (current.size == 5) {
// 현재 조합이 모든 시도의 조건을 만족하는지 확인합니다.
for ((i, query) in queries.withIndex()) {
if (current.count { it in query } != ans[i]) return
}
count++
return
}
for (num in start..n) {
current.add(num)
backtrack(num + 1, current)
current.removeAt(current.lastIndex)
}
}
backtrack(1, mutableListOf())
return count
}
// 아래는 예시 테스트 코드입니다.
fun main() {
val n = 10
val q = arrayOf(
intArrayOf(1, 2, 3, 4, 5),
intArrayOf(6, 7, 8, 9, 10),
intArrayOf(3, 7, 8, 9, 10),
intArrayOf(2, 5, 7, 9, 10),
intArrayOf(3, 4, 5, 6, 7)
)
val ans = intArrayOf(2, 3, 4, 3, 3)
println(solution(n, q, ans)) // 예상 출력: 3
}
🔍상세 설명
// 각 시도의 숫자 배열을 Set으로 변환하여 빠른 멤버십 검사를 수행합니다.
val queries = q.map { it.toSet() }입력받은 2차원 배열 q의 각 배열을 Set으로 변환합니다.
Set은 특정 원소가 포함되어 있는지 빠르게 검사할 수 있는 자료구조입니다.
current.count { it in query }각 숫자가 첫 번째 시도의 Set (setOf(1, 2, 3, 4, 5))에 포함되어 있는지 빠르게 확인할 수 있습니다. Set은 일반적으로 O(1)의 시간 복잡도로 멤버십 검사가 가능하므로, 효율성이 높아집니다. Set은 중복을 허용하지 않으므로, 혹시라도 중복된 숫자가 입력되어 있다면 자동으로 제거되어 올바른 결과를 얻을 수 있습니다.
current.count { it in query }는 Kotlin에서 컬렉션의 각 요소에 대해 주어진 조건(여기서는 it in query 조건)을 만족하는 요소들의 개수를 반환하는 함수입니다.
current.count { it in query }는 current 리스트의 각 요소에 대해 it in query 조건을 검사합니다.
• 여기서 it은 current의 각 요소를 의미합니다.
• 조건 it in query는 해당 숫자가 query Set 안에 있는지를 확인합니다.
따라서, 만약 current가 [3, 5, 7]이고, query가 setOf(1, 2, 3, 4, 5)라면,
• 숫자 3은 query에 포함되어 있으므로 조건을 만족합니다.
• 숫자 5도 조건을 만족합니다.
• 숫자 7은 query에 없으므로 조건을 만족하지 않습니다.
이 경우, current.count { it in query }는 2를 반환하게 됩니다.
for (num in start..n) {
current.add(num)
backtrack(num + 1, current)
current.removeAt(current.lastIndex)
}1. for (num in start..n):
start부터 n까지의 숫자 각각을 후보로 고려합니다.
백트래킹에서는 현재 선택할 수 있는 최소 숫자(start)를 정해 두어, 이전에 선택한 숫자보다 큰 숫자들만 선택하여 조합을 오름차순으로 만듭니다.
2. current.add(num):
현재 선택된 숫자(조합)를 기록하기 위해, for문에서 선택한 num을 current 리스트에 추가합니다.
예를 들어, current가 [3, 5]인 상태에서 num이 7이면, current는 [3, 5, 7]이 됩니다.
3. backtrack(num + 1, current):
재귀 호출을 통해, 현재 선택된 조합(current)을 바탕으로 다음 숫자를 선택합니다.
num + 1을 start로 전달하는 이유는, 이미 선택한 숫자보다 큰 숫자만 선택해서 조합의 오름차순을 유지하기 위함입니다.
4. current.removeAt(current.lastIndex):
재귀 호출이 끝난 후, 현재 조합에서 마지막으로 추가한 숫자를 제거합니다.
이 과정을 통해, 다른 가능한 숫자를 선택할 수 있도록 상태를 원래대로 복원(백트래킹)합니다.
📝예시
예를 들어, n이 10이고 현재 start가 3, current가 [3, 5]라고 가정합시다.
• for문은 3부터 10까지 순회하지만, start가 3이므로 실제로는 3이 아니라, 이전 단계에서 이미 3을 선택했으므로 num은 6부터 시작할 수도 있습니다.
• num이 7일 때, current에 7을 추가하면 [3, 5, 7]이 됩니다.
• 재귀 호출 backtrack(8, [3, 5, 7])을 통해, 8부터 10까지의 숫자 중 다음 숫자를 선택하는 과정을 진행합니다.
• 재귀 호출이 완료되면, 마지막에 추가했던 7을 제거하여 current를 다시 [3, 5]로 복원하고, 다음 후보 숫자(예: 8)를 추가하는 식입니다.
이렇게 하면 가능한 모든 조합을 체계적으로 탐색할 수 있습니다.
댓글