(BOJ) 16496 큰 수 만들기

16496 큰 수 만들기

• 분류 : Greedy / 문자열 / Sort

문제

음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

출력

리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.

예제 입력 1

5
3 30 34 5 9

예제 출력 1

9534330

예제 입력 2

5
0 0 0 0 1

예제 출력 2

10000

Solution - NumberFormat Exception

Exapnder

package boj

import java.util.*

private var N: Int = 0
private var input = mutableListOf<String>()


fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()
    for (i in 0 until N) {
        input.add(i, next())
    }
}

private fun solve() {
    if (input.map { it.toLong() }.sum() == 0L) {
        println("0")
        return
    }
    input.sortWith { str1: String, str2: String -> (str2 + str1).toLong() - (str1 + str2).toLong() }
    input.forEach {
        print("$it")
    }
    println()
}

Solution

Exapnder

package boj

import java.util.*

private var N: Int = 0
private var input = mutableListOf<String>()


fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()
    for (i in 0 until N) {
        input.add(i, next())
    }
}

private fun solve() {
    var result: Long = 0L
    for (i in 0 until N) {
        result += input[i].toLong()
    }

    if (result == 0L) {
        println("0")
        return
    }

    for (i in 0 until N) {
        for (j in 0 until N) {
            if (i == j) {
                continue
            }

            var left = (input[i] + input[j]).toLong()
            var right = (input[j] + input[i]).toLong()
            if (left - right > 0) {
                var tmp = input[i]
                input[i] = input[j]
                input[j] = tmp
            }

        }
    }
    input.forEach {
        print("$it")
    }
    println()
}

Point of Thinking

• 주어지는 배열을 input이라고 할때 input[i] + input[i + 1]과 input[i + 1] + input[i]를 비교하여 정렬하면 바로 해결
• 문제 제한 조건상 Int로 풀수가 없기때문에 Comparator를 제거하고 Bubble Sort를 응용해서 정렬하여 Accepted