백준 18870 좌표 압축 Kotlin (정렬)

문제 출처 : https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

알고리즘 분류

• 정렬
• 값 / 좌표 압축

풀이

간단한 정렬 문제이지만, 입력이 커서 아무 생각없이 풀면 시간 초과가 뜰 것이다.

또한, 언어에 따라 풀이가 조금씩 다르다.

 

본인은 Kotlin 언어로 풀었고, .distinct()함수를 이용했다.

sort()는 웬만한 언어에 다 있을 거고, 해쉬 맵도 마찬가지다.

.distinct()는 다른 언어에도 있는지 모르겠다.

.distinct()는 배열 내에 중복 요소들을 제거해준다.

.distinct()로 중복을 제거하고 이를 오름차순 정렬한 배열을 sortedArr에 저장한다.

중복을 제거하고 오름차순하였으니

sortedArr[i]는 곧 Xi이고,

i는 Xi보다 작은 수들의 개수이다.

HashMap을 이용해 key == sortedArr[i]에 value == i를 저장한다.

 

이후 원본 arr을 돌면서 해쉬맵에 저장된 값을 출력하면 끝!

 

아래 코드2는 이분 탐색 풀이이다.

이분 탐색을 이용하면 더 효율적으로, 짧은 코드로 풀 수 있다.

코드1

val br = System.`in`.bufferedReader()

fun main() =with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()
    var arr = br.readLine().split(' ').map{it.toInt()}
    val sortedArr = arr.distinct().sorted()
    val hashMap = HashMap<Int,Int>()
    var idx=0
    sortedArr.forEach {
        hashMap[it]=idx++
    }

    for(i in 0 until n){
        write("${hashMap.get(arr[i])} ")
    }

    close()
}

코드2

val br = System.`in`.bufferedReader()

fun main() =with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()
    var arr = br.readLine().split(' ').map{it.toInt()}
    val sortedArr = arr.distinct().sorted()
    for(i in 0 until n){
        write("${sortedArr.binarySearch(arr[i])} ")
    }

    close()
}