백준 2608번: 로마 숫자

문제: https://www.acmicpc.net/problem/2608

문제 풀이

구현

toNumber(s) = 로마 숫자를 아라비아 숫자로 변환해 반환하는 함수

toRomeNumber(n) = 아라비아 숫자를 로마 숫자로 변환해 반환하는 함수

로마 숫자의 문자를 앞에서부터 하나하나 확인하며 다음 문자가 현재 문자보다 작은 수면 그대로 result에 값을 더하고 다음 문자가 더 크다면 다음 문자와 현재 문자의 차이만큼 result에 더해 마지막으로 result에 저장된 값을 반환하는 toNumber(s) 함수를 이용해 입력받은 두 로마 숫자를 아라비아 숫자로 변환해서 더하고 출력함

이 합을 로마 숫자가 큰 문자부터 사용된다는 점을 이용해 로마 숫자에 사용되는 문자를 단위별로 구분해서 값이 큰 문자부터 사용해 로마 숫자로 변환해서 출력하면 정답

풀이 설명

로마 시대 때는 현재 사용하는 아라비아 숫자가 아닌 다른 방법으로 수를 표현하였다.

로마 숫자는 다음과 같은 7개의 기호로 이루어진다.

기호	I	V	X	L	C	D	M
값	1	5	10	50	100	500	1000

수를 만드는 규칙은 다음과 같다.

1. 보통 큰 숫자를 왼쪽에 작은 숫자를 오른쪽에 쓴다. 그리고 그 값은 모든 숫자의 값을 더한 값이 된다. 예를 들어 LX = 50 + 10 = 60 이 되고, MLI = 1000 + 50 + 1 = 1051 이 된다.
2. V, L, D는 한 번만 사용할 수 있고 I, X, C, M은 연속해서 세 번까지만 사용할 수 있다. 예를 들어 VV나 LXIIII 와 같은 수는 없다. 그리고 같은 숫자가 반복되면 그 값은 모든 숫자의 값을 더한 값이 된다. 예를 들어 XXX = 10 + 10 + 10 = 30 이 되고, CCLIII = 100 + 100 + 50 + 1 + 1 + 1 = 253 이 된다.
3. 작은 숫자가 큰 숫자의 왼쪽에 오는 경우는 다음과 같다. IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900 을 나타낸다. 이들 각각은 한 번씩만 사용할 수 있다. 그런데 IV 와 IX 는 같이 쓸 수 없으며 XL 과 XC, CD 와 CM 또한 같이 쓸 수 없다. 이들 외에는 작은 숫자가 큰 숫자 왼쪽 어디에도 나올 수 없다. 예를 들어 XCXC 나 CMCD, VX 나 IIX 와 같은 수는 없다. 참고로 LIX = 50 + 9 = 59, CXC = 100 + 90 = 190 이 된다.
4. 모든 수는 가능한 가장 적은 개수의 로마 숫자들로 표현해야 한다. 예를 들어 60 은 LX 이지 XLXX 가 아니고, 5 는 V 이지 IVI 가 아니다.

로마 숫자로 표현된 두 수의 합을 아라비아 숫자, 로마 숫자로 출력해야 하므로 로마 숫자를 아라비아 숫자로 바꾸는 것, 아라비아 숫자를 로마 숫자로 바꾸는 두 가지 기능이 필요하다.

먼저 로마 숫자를 아라비아 숫자로 바꾸는 과정부터 살펴보면 다음과 같다.

1. 앞에서 부터 문자가 어떤 숫자인지 확인한다.
2. 수를 만드는 방법에 의해 기본적으로 큰 수의 문자가 앞으로 오는데 3번 조건에 따라 뒤에 오는 문자가 더 클 경우가 있다.
3. 그러므로 문자를 확인할 때 다음 문자가 더 큰 경우가 아니라면 그대로 문자를 숫자로 변환하면 되고 아니라면 뒤의 문자까지 숫자로 변환하면 된다.

이 과정에 따라 입력 받은 두 수를 아라비아 숫자로 변환해 합을 구하고 출력을 한다.

그 이후에 이 수를 로마 숫자로 출력해야 하므로 다음 과정을 거쳐 로마 숫자로 변환한다.

1. 로마 숫자는 큰 수부터 출력해야 하므로 단위가 되는 숫자들을 먼저 나눈다. 이 때 CM, CD와 같이 한 번만 사용되는 숫자도 단위로 들어가야 한다.
2. 단위 숫자를 하나씩 확인하며 현재 수가 이 단위보다 크다면 단위의 문자를 쓰고 단위만큼의 숫자를 뺀다.
3. 2번 과정을 현재 수가 0이 될때까지 반복함

CM, CD와 같은 숫자들도 단위로 들어가는 이유를 설명하면 먼저 기본적으로 단위를 나타내는 수를 살펴보면 자릿수마다 1, 5를 나타내는 숫자가 있고, 같은 문자를 세 번 이상 사용하지 않는다는 점에서 자릿수의 4를 나타내려면 특별히 문자가 있는 것이 아니라면 1을 나타내는 문자를 4번 사용해야 한다는 점에서 수를 나타내는 조건의 모순이 생기게 된다.

9를 나타내는 경우도 5를 나타내는 문자를 사용한 이후에 1을 나타내는 문자를 4번 사용하기 때문에 문제가 생긴다. 따라서 문자를 나타내는 조건을 맞추기 위해 4, 9를 나타내는 특수 문자 CM, CD, XC, XL, IX, IV도 단위로 인정하는 것이다.

이에 따라 로마 숫자도 출력하면 정답이 된다.

소스 코드

fun main(){
    fun toNumber(s: String): Int {
        var result = 0
        var idx = 0

        fun value(romeNum: Char) = when (romeNum) {
            'I' -> 1
            'V' -> 5
            'X' -> 10
            'L' -> 50
            'C' -> 100
            'D' -> 500
            'M' -> 1000
            else -> 0
        }

        while (idx < s.length) {
            val romeNum = s[idx]
            val v1 = value(romeNum)
            if (idx + 1 < s.length) {
                val nextRomeNum = s[idx + 1]
                val v2 = value(nextRomeNum)
                if (v1 < v2) {
                    result += (v2 - v1)
                    idx += 2
                    continue
                }
            }
            result += v1
            idx++
        }
        return result
    }
    val num = toNumber(readln()) + toNumber(readln())
    println(num)
    fun toRomeNumber(n: Int): String {
        var x = n
        val sb = StringBuilder()

        val nums = intArrayOf(
            1000, 900, 500, 400,
            100, 90, 50, 40,
            10, 9, 5, 4, 1
        )
        val romes = arrayOf(
            "M", "CM", "D", "CD",
            "C", "XC", "L", "XL",
            "X", "IX", "V", "IV", "I"
        )

        for (i in nums.indices) {
            while (x >= nums[i]) {
                x -= nums[i]
                sb.append(romes[i])
            }
        }
        return sb.toString()
    }
    println(toRomeNumber(num))
}