[백준] 18870 좌표 압축

 

 

🔒 문제

 

 

🧠 접근 방법

문제풀이 자체보다 이 문제에서 요구하는 아이디어에서 얻어갈게 많다.

 

 

수의 범위와 개수가 클 때
순서대로 index 를 두고
해당 숫자를 저장-조회 할 수 없을까?

 

수의 범위가 크고 갯수가 많은 경우 무조건 큰 배열을 선언해서 대소비교를 하기보다 10, 15, 4, 4, 11, 14 이렇게 있다면 

중복을 제거한 (4, 10, 11, 14, 15) 로 만들고 원하는 숫자를 입력했을 때 중복 제거한 배열 내에서 인덱스만 return 하면 된다.

4 -> 0

10 -> 1

11 -> 2

14 -> 3

15 -> 4

 

 

🔑 Kotlin Code

자신보다 작은 크기의 원소의 중복 제거 값을 얻기위해

1. 오름차순 정렬
2. 중복 원소 제거
3. 원본 배열로부터 하나씩 해당 원소의 인덱스를 1, 2에서 만든 배열 내에서 index 를 뽑아옴.

import java.io.BufferedReader
import java.io.InputStreamReader

// lower bound 구하는 이분 탐색
private fun getBinarySearchLowerBoundIndex(nums: List<Int>, target: Int): Int {
    var left = 0
    var right = nums.size

    while (left < right) {
        val mid = (left + right) / 2
        if (nums[mid] >= target) right = mid
        else left = mid + 1
    }

    return left
}


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    br.readLine().toInt()
    val originalNums = br.readLine().split(" ").map(String::toInt).toIntArray()
    val sortedNums = originalNums.sorted().distinct()

    val stringBuilder = StringBuilder()

    for (targetNum in originalNums) {
        val lowerBoundIdx = getBinarySearchLowerBoundIndex(sortedNums, targetNum)
        stringBuilder.append(lowerBoundIdx).append(" ")
    }

    print(stringBuilder)
}