[백준] 18870 (좌표 압축)

#1 알고리즘

#1-1 '정렬' 문제

결국 제일 작은 원소는 0이라는 값으로 '압축'될 것이고, 그 다음 순서로 큰 원소는 1이 된다. 즉, 이 문제는 순서 문제고 순서를 부여하기 위해선 정렬이 요구된다. 따라서 이 문제는 정렬 문제다.
 

#1-2 병합 정렬

정렬 - 병합 정렬 (Merge Sort)

정렬 알고리즘으로 병합 정렬을 사용했다.
 

#1-3 map의 활용

이 문제는 '순서' 즉 배열에서 index에 해당하는 부분을 출력하는 문제다. 정렬이 완료된 Array를 순회하며 해당 Array의 index와 value를 Map에 할당할 것이다 (삽입 및 조회 시 O(1)의 시간복잡도를 지니는 HashMap을 사용한다).
 

2 4 -10 4 -9

테스트 케이스로 위와 같은 배열이 주어졌다고 해보자. 이 배열을 정렬하면,
 

-10 -9 2 4 4

이 된다. 각 원소의 인덱스는 정렬된 순서대로
 

0 1 2 3 4

가 될 것인데 3번 인덱스와 4번 인덱스는 그 인덱스가 가리키는 값이 4로 서로 동일하다. 이 경우는 가장 먼저 나온 인덱스인 3을 4의 인덱스로서 Map에 등록한다. 그 알고리즘을 코드로 나타내면 아래와 같다.
 

var previousElement: Int? = null
var index = -1
for (i: Int in sortedArray.indices) {
    if (previousElement != sortedArray[i]) {
        map[sortedArray[i]] = ++index
        previousElement = sortedArray[i]
    }
}

 

#2 코드 - 코틀린

import java.io.BufferedWriter
import java.io.OutputStreamWriter

lateinit var array: Array<Int>
val map = HashMap<Int, Int>()

fun main() {
    // Input을 토대로 array 만들기
    val arraySize = readln().toInt()
    array = Array(arraySize) { -1 }
    val stringArray = readln().split(" ")
    for (i: Int in 0..<arraySize) {
        val intElement = stringArray[i].toInt()
        array[i] = intElement
    }

    // array를 깊은 복사하고, 정렬까지한 sortedArray 만들기
    val sortedArray = array.copyOf()
    mergeSort(sortedArray, 0, sortedArray.size - 1)

    // key가 sortedArray의 index고 value는 sortedArray의 element값인, map 만들기 (단, 마치 중복되는 원소가 없는 것처럼 처리)
    var previousElement: Int? = null
    var index = -1
    for (i: Int in sortedArray.indices) {
        if (previousElement != sortedArray[i]) {
            map[sortedArray[i]] = ++index
            previousElement = sortedArray[i]
        }
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    for (i: Int in 0..<arraySize) {
        bw.write("${map[array[i]]} ")
    }
    bw.flush()
    bw.close()
}

fun mergeSort(array: Array<Int>, startIndex: Int, endIndex: Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if (startIndex < endIndex) {
        val midIndex = (startIndex + endIndex) / 2
        mergeSort(array, startIndex, midIndex)
        mergeSort(array, (midIndex + 1), endIndex)

        merge(array, startIndex, midIndex, endIndex)
    }
}

fun merge(array: Array<Int>, startIndex: Int, midIndex: Int, endIndex: Int) {
    // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f
    var f = startIndex // f의 최댓값은 midIndex

    // array에서 나뉜 's'econd 부분을 순회할 인덱스 s
    var s = midIndex + 1 // s의 최댓값은 endIndex

    // 'T'emporary 배열 그리고 이 배열을 순회할 인덱스 t
    val T: Array<Int> = Array(endIndex - startIndex + 1) { 0 }
    var t = 0

    while (f <= midIndex && s <= endIndex) {

        if (array[f] < array[s]) {
            T[t++] = array[f++]

        } else {
            T[t++] = array[s++]
        }
    }

    // f의 영역이 남았다면 비워준다
    while (f <= midIndex) {
        T[t++] = array[f++]
    }

    // s의 영역이 남았다면 비워준다
    while (s <= endIndex) {
        T[t++] = array[s++]
    }

    for (i: Int in 0..(T.size - 1)) {
        array[startIndex + i] = T[i]
    }
}