Kotlin 🍬 백준 13단계 :: 18870 번

좌표 압축

문제   |

  수직선 위에 N개의 좌표 $X_{1}$, $X_{2}$, ..., $X_{N}$이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

  $X_{i}$를 좌표 압축한 결과 $X'_{i}$의 값은 $X_{i}$ > $X_{j}$를 만족하는 서로 다른 좌표 $X_{j}$의 개수와 같아야 한다.

  $X_{1}$, $X_{2}$, ..., $X_{N}$에 좌표 압축을 적용한 결과 $X'_{1}$, $X'_{2}$, ..., $X'_{N}$를 출력해보자.

 

입력   |

  첫째 줄에 N이 주어진다.

  둘째 줄에는 공백 한 칸으로 구분된 $X_{1}$, $X_{2}$, ..., $X_{N}$이 주어진다.

 

출력   |

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

 

제한   |

• 1 ≤ N ≤ 1,000,000
• -109 ≤ $X_{i}$ ≤ 109

 

 

풀이  |

  1. 낮은 값이 높은 순위를 갖는다. (가장 높은 순위는 0순위다.)

  2. 중복되는 원소는 같은 순위를 갖는다.

 

 

답안  |

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val N = nextInt()
    val arr = mutableSetOf<String>()

    repeat(N) {
        arr.add(next())
    }
    
    val sortedArr = arr.distinct().sorted()
    for (i in 0 until N) {
        print(sortedArr.binarySearch(arr.elementAt(i)).toString() + " ")
    }
}

위 코드로 시간초과가 발생했다.

그래서 수정한 코드

fun main() {
    with(System.`in`.bufferedReader()) {
        with(System.out.bufferedWriter()) {
            val N = readLine().toInt()
            val arr = readLine().split(" ").map(String::toInt)
            val sortedArr = arr.distinct().sorted()
            
            for (i in 0 until N) {
                write(sortedArr.binarySearch(arr[i]).toString() + " ")
            }

            close()
        }
        close()
    }
}