[백준 1017] 소수 쌍

백준 1017번: 소수 쌍 - 상세 풀이

🔍 1. 문제 소개

백준 1017번 "소수 쌍" 문제는 주어진 짝수 개의 정수 리스트에서 두 수를 짝지어, 각 쌍의 합이 소수가 되도록 하는 문제입니다. 모든 수를 짝지어야 하며, 첫 번째 수와 짝지어진 수를 오름차순으로 출력해야 합니다. 만약 모든 수를 소수의 합으로 짝지을 수 없다면 -1을 출력합니다.

💡 2. 문제 해석

문제의 핵심은 주어진 정수 리스트를 효율적으로 탐색하여 모든 수를 소수의 합으로 짝짓는 것입니다. 문제의 제약 조건은 다음과 같습니다:

* 리스트의 크기 N은 짝수이며, 50보다 작거나 같습니다 (2 ≤ N ≤ 50). * 리스트에 있는 수는 1,000보다 작거나 같은 자연수이며, 중복되지 않습니다.

문제 해결의 어려움은 모든 가능한 짝짓기 경우의 수를 탐색해야 한다는 점에 있습니다. 단순히 모든 조합을 시도하는 것은 시간 초과를 유발할 수 있습니다.

🧠 3. 접근 방법

이 문제는 백트래킹(Backtracking) 알고리즘을 사용하여 해결할 수 있습니다. 백트래킹은 모든 가능한 경우의 수를 탐색하지만, 불필요한 가지를 가지치기하여 효율성을 높이는 기법입니다.

알고리즘의 핵심 아이디어는 다음과 같습니다:

1. **정렬:** 입력 리스트를 오름차순으로 정렬합니다. 정렬을 통해 탐색 과정을 효율적으로 만들 수 있습니다.

2. 재귀 함수: 재귀 함수를 사용하여 짝짓기를 진행합니다. 각 수에 대해 아직 짝지어지지 않은 다른 수들과의 합이 소수인지 확인합니다. 3. 백트래킹: 만약 현재 수에 대해 짝을 찾지 못하거나, 모든 수를 짝짓지 못한 경우, 이전 단계로 돌아가 다른 짝짓기를 시도합니다. 4. 결과 저장: 모든 수가 짝지어지면, 첫 번째 수와 짝지어진 수를 저장하고 재귀를 종료합니다. 5. 결과 출력: 저장된 결과를 오름차순으로 정렬하여 출력합니다. 만약 짝짓기에 실패하면 -1을 출력합니다.

⚙️ 4. 구현 과정

1. 입력을 받고 리스트를 정렬합니다.

2. isPrime 함수를 정의하여 소수 판별을 수행합니다. 3. 재귀 함수 findPairs를 정의하여 백트래킹 알고리즘을 구현합니다. 이 함수는 현재 인덱스부터 시작하여 짝을 찾고, 다음 인덱스로 재귀 호출을 합니다. 짝을 찾지 못하면 false를 반환하고, 모든 수를 짝지으면 true를 반환합니다. 4. findPairs 함수의 결과에 따라 성공 여부를 판단하고 결과를 출력합니다.

💻 5. 코드 설명

import java.util.*

fun isPrime(n: Int): Boolean {
    if (n <= 1) return false
    if (n <= 3) return true
    if (n % 2 == 0 || n % 3 == 0) return false
    var i = 5
    while (i * i <= n) {
        if (n % i == 0 || n % (i + 2) == 0) return false
        i += 6
    }
    return true
}

fun main() {
    val n = readLine()!!.toInt()
    val nums = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    Arrays.sort(nums)
    val used = BooleanArray(n)
    val result = IntArray(n)

    fun findPairs(index: Int): Boolean {
        if (index == n) return true
        if (used[index]) return findPairs(index + 1)
        for (i in index + 1 until n) {
            if (!used[i] && isPrime(nums[index] + nums[i])) {
                used[index] = used[i] = true
                result[index] = nums[i]
                if (findPairs(index + 1)) return true
                used[index] = used[i] = false
            }
        }
        return false
    }

    if (findPairs(0)) {
        Arrays.sort(result)
        println(result.filter { it != 0 }.joinToString(" "))
    } else {
        println("-1")
    }
}

* isPrime(n): 6k ± 1 최적화를 사용한 소수 판별 함수. * main() 함수: 입력을 받고 정렬하며, 백트래킹 함수 findPairs를 호출합니다. * findPairs(index): 재귀 함수로, 현재 인덱스부터 시작하여 짝을 찾고 백트래킹을 수행합니다. used 배열은 이미 사용된 수를 추적합니다. result 배열은 각 수의 짝을 저장합니다.

⏱️ 6. 시간 복잡도와 공간 복잡도 분석

* 시간 복잡도: 최악의 경우 모든 가능한 짝짓기를 탐색해야 하므로, 시간 복잡도는 O(n!)에 가까워집니다. 하지만 입력 크기가 제한되어 있으므로 (n ≤ 50), 실행 가능한 시간 내에 결과를 얻을 수 있습니다. isPrime 함수는 O(√n)의 시간 복잡도를 가지지만, 전체 시간 복잡도에 비해 지배적이지 않습니다. * 공간 복잡도: used 배열과 result 배열에 O(n)의 공간이 필요합니다. 재귀 호출 스택도 최악의 경우 O(n)의 공간을 사용할 수 있습니다. 따라서 전체 공간 복잡도는 O(n)입니다.

🎯 7. 결론

이 문제는 백트래킹 알고리즘을 사용하여 효율적으로 해결할 수 있습니다. 입력 크기 제한 덕분에 O(n!)의 시간 복잡도에도 불구하고 실행 가능한 시간 내에 문제를 해결할 수 있습니다. 하지만 입력 크기가 더 커진다면, 보다 효율적인 알고리즘 (예: 그래프 이론을 이용한 최대 매칭 알고리즘)을 고려해야 합니다. 소수 판별 함수의 최적화도 전체 실행 시간에 영향을 미치므로, 효율적인 소수 판별 방법을 사용하는 것이 중요합니다.