[백준 16496번] [Kotlin] 큰 수 만들기

https://www.acmicpc.net/problem/16496

16496번: 큰 수 만들기

난이도 : 플래티넘 4
태그 : 그리디, 정렬

 

 

1. 설명

문제 자체는 간단합니다.

n과, n개의 숫자가 주어질 때 해당 숫자를 잘 조합하여 가장 큰 수를 만드는 문제입니다.

 

 

 

2. 소스코드

2.1. 첫 번째 시도

      

      

      

    
    

      <kotlin />
    
import java.util.StringTokenizer

fun main() {
    val n = readln().toInt()
    val st = StringTokenizer(readln())
    val arr = Array<String>(n) { st.nextToken() }

    val sb = StringBuilder()
    arr.sortedByDescending { it }.forEach {
        sb.append(it)
    }

    print(sb)
}

 

그냥 사전순으로 내림차순 정렬하면 될 것 같은데? 라는 생각에 코드를 작성하였으나...

 

5

3 30 34 5 9를 넣었을 떼,

9534330이 나와야 하는데 9534303이 나와서 실패.

사전순으로 내림차순 정렬한다면 30이 3보다 앞서 나오기 때문이였습니다.

 

 

 

2.2. 두 번째 시도

      

      

      

    
    

      <kotlin />
    
fun main() {
    val n = readln().toInt()
    val arr = readln().split(" ")

    if (arr.all { it == "0" }) {
        println(0)
        return
    }

    arr.sortedWith { o1, o2 ->
        if (o1 + o2 < o2 + o1) 1 else -1
    }.joinToString("").let(::println)
}

 

 

정렬 조건을 o2, o1를 이어 붙인것이 o1에 o2를 이어붙인 것보다 클 때 앞서 오도록 정렬 조건을 지정해줬습니다.

또, 모든 숫자가 0일 경우, 답은 0 하나만 출력되야 하므로

모든 숫자가 0인지 확인하는 코드도 넣어줬습니다.

 

 

다행이도 통과하였습니다.

 

 

 

3. 후기

P5지만 생각보다 간단하게 풀린 문제였습니다.

정렬 조건 지정에 관한 테크닉을 또 하나 배웠네요.