[백준/BOJ] 18870번: 좌표 압축

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를 출력해보자.

해설

문제가 잘 이해가 안갔으나 예제를 보니 정렬해서 몇번째에 위치하는지를 출력하는 것이라 생각했다.

이를 풀기 위해 원본 배열과 정렬할 배열, 정렬했을 때의 키와 위치를 저장할 map을 선언하였다.

 

문제를 푸는 법은 어렵지 않다.

1. 원본 배열을 입력하고 정렬할 배열에 복사하여 정렬시킨다.

2. 정렬한 배열을 반복문을 돌려 map에 키가 없다면 키와 몇번째인지(값)을 넣어준다.

3. 원본 배열과 map을 비교하며 원하는 값을 뽑는다.

 

이 3가지를 코드로 작성하면 다음과 같다.

소스 코드

import java.lang.StringBuilder
import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    val n = readLine().toInt()
    val origin = IntArray(n)
    val sorted = IntArray(n)
    val st = StringTokenizer(readLine())
    repeat(n) { i->
        origin[i] = st.nextToken().toInt()
        sorted[i] = origin[i]
    }
    sorted.sort()

    val map = HashMap<Int, Int>()
    var rank = 0
    for(i in sorted) {
        if(!map.containsKey(i)) {
            map.put(i, rank)
            rank++
        }
    }
    for(i in origin) {
        sb.append("${map[i]} ")
    }
    println(sb.toString())
}