[백준] 2915: 로마 숫자 재배치 (python 파이썬)

해당 문제는 로마 숫자가 주어졌을 때 로마 문자들을 재배치하여 가장 작을 수를 찾아내는 문제다. 입력으로 주어지는 로마 숫자는 1~99까지의 양수이고, 우리가 만들 수 있는 수 역시 1~99까지의 수 밖에 되지 않으므로 Brute Force를 사용하기로 결정했다. 처음으로 떠올린 방법은 I, V, X, L, C의 개수에 따라 최소값을 모두 구하는 방식이다. 즉, I가 1개인 경우, I가 1개, X가 2개인 경우 등 모든 경우를 살펴보고, 해당 경우들의 최소값을 미리 배열에 저장하는 것이다. 따라서 입력으로 받아온 문자의 I, V, X, L, C의 개수를 보고 우리는 구했던 최소값을 찾아 출력하면 된다. 이를 위해 크기가 128인 배열 하나를 선언했다. 그리고 조합 가능한 모든 문자열을 살펴보며 (I의 개수)×1+(X의 개수)×4+(V의 개수)×16+(L의 개수)×32+(C의 개수)×64의 인덱스에 저장된 값이 없다면 저장하는 코드를 작성했다. 말이 이해가 어려울 수 있는데 아래 코드를 살펴보면 이해할 수 있다.

import sys
input = sys.stdin.readline

def checkIndex(string: str):
    # 위에서 설명한 인덱스 방식에 따라 인덱스를 계산하는 함수다.
    index = 0
    for char in string:
        if char == "I":
            index += 1
        elif char == "X":
            index += 3
        elif char == "V":
            index += 16
        elif char == "L":
            index += 32
        elif char == "C":
            index += 64
    return index

# 이후 1~100까지의 수를 하나씩 살펴보기 위해 1의 자리와 2의 자리 표현을 각각 저장한다.
oneUnitsRoma:list = ["I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
twoUnitsRoma:list = ["X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]

# 128 크기의 배열을 하나 선언한다.
results: list = [0 for _ in range(128)]

# 1~9까지의 경우를 먼저 살펴본다.
for i in range(9):
    string = oneUnitsRoma[i]
    
    index = checkIndex(string)
    if results[index] == 0:
        results[index] = string

# 10~99까지의 경우를 살펴본다.
for i in range(9):
    index = checkIndex(twoUnitsRoma[i])
    if results[index] == 0:
        results[index] = twoUnitsRoma[i]
        
    for j in range(9):
        string = twoUnitsRoma[i]+oneUnitsRoma[j]
        
        index = checkIndex(string)
        if results[index] == 0:
            results[index] = string 

# 입력된 스트링의 I, V, X, L, C의 개수를 찾아 해당 경우의 최소값을 찾고 출력한다.
inputString:str = input().rstrip()
index = checkIndex(inputString)
print(results[index])

위 코드는 약 100개의 경우를 살피고, 각 경우 문자열 최대 길이 8만큼의 시간 소요가 필요하므로 약 800번의 연산이 필요하다.

 

위 방법을 떠올리고 좀 더 쉬운 방법이 없을까 생각해봤다. 그러다 "정렬"을 사용한 방식을 떠올렸다. 위 코드는 모든 가능한 문자열의 "I, V, X, L, C"의 개수를 세고 각 경우의 최소값을 구하는 방식이었다. 하지만 결국 "I, V, X, L, C"의 개수가 같다는 것은 정렬한 경우 string의 상태가 같음을 의미한다. 즉, 1~99까지의 모든 경우를 정렬하면서 입력받은 스트링의 정렬 상태와 같은 최초의 상태가 바로 최소값이 된다. 이 경우 문자열 최대 길이 8을 정렬하는 3만큼의 시간 소요와 입력받은 스트링의 정렬 상태와 같은지 확인할 때 8만큼의 연산이 발생한다. 따라서 각 경우 11번의 연산이 필요하다. 즉, 최악의 경우 약 1100번의 연산이 필요하다. 하지만 이 경우 최소값을 발견하면 바로 멈춘다는 장점이 있다. 단, 제출 결과는 둘 모두 44ms로 동일하게 나왔다.

import sys
input = sys.stdin.readline

oneUnitsRoma:list = ['', "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
twoUnitsRoma:list = ['', "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]

# 입력된 스트링은 먼저 정렬한다.
inputString:str = sorted(input().rstrip())

for i in range(1, 100):
    string = twoUnitsRoma[i//10]+oneUnitsRoma[i%10]
    # 정렬한 입력 스트링과 현재 살펴보는 스트링의 정렬 상태가 같다면 해당 스트링을 출력한다 
    if inputString==sorted(string): 
        print(string)
        break