[백준 1015] 수열 정렬

백준 1015번: 수열 정렬 - 상세 풀이

🔍 1. 문제 소개

이 문제는 길이 N인 배열 A가 주어졌을 때, 0부터 N-1까지의 수를 한 번씩 포함하는 순열 P를 찾는 문제입니다. 이 순열 P를 배열 A에 적용하면 (B[P[i]] = A[i]) 결과 배열 B가 비내림차순이 되어야 합니다. 만약 여러 개의 순열 P가 조건을 만족한다면, 사전순으로 가장 앞서는 순열을 출력해야 합니다.

💡 2. 문제 해석

문제의 핵심은 배열 A의 원소들을 비내림차순으로 정렬했을 때, 각 원소의 원래 위치를 기억하는 순열 P를 찾는 것입니다. 즉, A를 정렬했을 때, 정렬된 배열에서 각 원소의 원래 인덱스를 찾아 순열 P를 구성해야 합니다. 제약 조건으로는 N의 크기가 50 이하이며, A의 원소는 1000 이하의 자연수라는 점입니다.

🧠 3. 접근 방법

문제를 해결하기 위한 가장 효율적인 방법은 다음과 같습니다.

1. **정렬된 인덱스 배열 생성:** 배열 A의 원소들을 정렬할 때, 각 원소의 원래 인덱스를 함께 기억하는 방법을 사용합니다. 이는 `IntArray`를 사용하여 인덱스를 저장하고, `sortedWith`와 `compareBy`를 이용하여 A의 값을 기준으로 정렬하면 됩니다.

2. 순열 P 생성: 정렬된 인덱스 배열을 이용하여 순열 P를 생성합니다. 정렬된 인덱스 배열의 i번째 원소는 A에서 i번째로 작은 원소의 원래 인덱스를 나타냅니다. 따라서, P[정렬된 인덱스[i]] = i 로 설정하면 됩니다.

이 방법을 통해 A를 비내림차순으로 정렬하는 순열 P를 효율적으로 찾을 수 있습니다.

⚙️ 4. 구현 과정

1. 입력으로 배열 A의 크기 N과 배열 A의 원소들을 입력받습니다.

2. 0부터 N-1까지의 인덱스를 가지는 sortedIndices 배열을 생성합니다. 3. sortedIndices 배열을 A의 원소 값을 기준으로 정렬합니다. 4. p 배열을 생성하고, sortedIndices 배열을 이용하여 순열 P를 계산합니다. p[sortedIndices[i]] = i를 통해 각 원소의 정렬 후 위치를 저장합니다. 5. p 배열을 출력합니다.

💻 5. 코드 설명

import java.util.*
import kotlin.Comparator

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray()

    val sortedIndices = IntArray(n) { it }
    val comparator = Comparator { i1, i2 -> a[i1].compareTo(a[i2]) }
    sortedIndices.sortWith(comparator)

    val p = IntArray(n)
    for (i in 0 until n) {
        p[sortedIndices[i]] = i
    }

    println(p.joinToString(" "))
}

* readLine()!!.toInt(): 입력으로부터 정수를 읽어옵니다. * readLine()!!.split(" ").map { it.toInt() }.toIntArray(): 입력으로부터 공백으로 구분된 정수들을 읽어와 IntArray로 변환합니다. * IntArray(n) { it }: 0부터 n-1까지의 숫자를 가지는 IntArray를 생성합니다. 이는 원래 배열 A의 인덱스를 나타냅니다. * val comparator = Comparator<Int> { i1, i2 -> a[i1].compareTo(a[i2]) }: sortedIndices 배열을 정렬하기 위한 비교 로직을 정의하는 Comparator를 생성합니다. 이 Comparator는 배열 `a`의 해당 인덱스에 있는 값을 기준으로 두 인덱스를 비교합니다. * sortedIndices.sortWith(comparator): sortedIndices 배열을 생성된 Comparator를 사용하여 정렬합니다. * p[sortedIndices[i]] = i: 정렬된 인덱스 sortedIndices[i]를 사용하여 순열 p를 생성합니다. sortedIndices[i]는 A에서 i번째로 작은 원소의 원래 인덱스이므로, 이 원소의 새로운 위치는 i가 됩니다. * println(p.joinToString(" ")): 결과 배열 p를 공백으로 구분하여 출력합니다.

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

* 시간 복잡도: sortedIndices 배열의 정렬에 O(N log N)의 시간이 소요됩니다. 나머지 연산들은 O(N) 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N log N) 입니다.

* 공간 복잡도: a, sortedIndices, p 배열을 저장하는데 O(N)의 공간이 필요합니다. 따라서 전체 공간 복잡도는 O(N) 입니다.

🎯 7. 결론

이 문제는 배열의 정렬과 인덱스 관리를 통해 효율적으로 해결할 수 있습니다. Comparator와 sortWith를 사용하여 인덱스를 기반으로 정렬하는 기법을 활용하면 문제를 정확하고 효율적으로 해결할 수 있습니다. O(N log N)의 시간 복잡도와 O(N)의 공간 복잡도는 이 문제에 대한 적절한 해결책입니다.