(Python) 알고리즘 문제 D+6

Kepler·2020년 2월 17일
0

알고리즘

목록 보기
7/8

문제:

로마자에서 숫자로 바꾸기

1~3999 사이의 로마자 s를 인자로 주면 그에 해당하는 숫자를 반환해주세요.
로마 숫자를 숫자로 표기하면 다음과 같습니다.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

로마자를 숫자로 읽는 방법은 로마자를 왼쪽부터 차례대로 더하면 됩니다.
III = 3
XII = 12
XXVII = 27
입니다.

그런데 4를 표현할 때는 IIII가 아니라 IV 입니다.
뒤의 숫자에서 앞의 숫자를 빼주면 됩니다.
9는 IX입니다.

I는 V와 X앞에 와서 4, 9
X는 L, C앞에 와서 40, 90
C는 D, M앞에 와서 400, 900


Roman to num (MMM -> 3000)

해답 (model solution_1)

def roman_to_num(s):
        rom = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        int = 0
        for i in range(len(s)):
            if i > 0 and rom[s[i]] > rom[s[i - 1]]:
                int += rom[s[i]] - 2 * rom[s[i - 1]]
            else:
                int += rom[s[i]]
        return int
  • 1~1000중 다른수를 만드는 기준이 되는 unique한 로마숫자와 그에 대응하는 정수를 딕셔너리에 저장했다.
  • int를 0 으로 정의했다. 이곳에 convert한 로마숫자의 정수 값을 더해나갈 것이다.
  • 주어진 로마숫자의 길이만큼 for문을 돌려, 한 글자씩 대입해가며 알맞은 정수를 찾는다.
    • 0번째 인덱스의 로마숫자에 알맞는 정수를 찾아 int에 더해나간다.
    • 1번째 인덱스부터는 해당 인덱스의 정수가 그 전 인덱스의 정수보다 큰지를 비교한다. 해당 인덱스가 전 인덱스 정수보다 큰 경우는 오직4,9,40,90,400,900 뿐이다. 이들은 rom의 로마 숫자에서 1 또는 10 또는 100만큼을 뺀 값으로 represent된다 (예: 4는 IV(V-I), 9는 XC(C-X), 900은 CM(M-C).) 따라서 여기에 해당되는 경우, 해당 인덱스의 정수값을 int에 더하고 동시에 이전 step에서 더해주었던 전 인덱스의 값을 두번 빼주어야 한다.
      예) XXIV (24) 의 경우, 각각의 숫자를 대입하여 계산하면 10+10+1+5 = 27이 된다. I는 0으로, V는 4로 환산되어야 하기 때문에, I를 두번 빼 주어 24를 만든다.
    • 위의 경우에 해당하지 않을 경우, 0이후 인덱스도 int에 차례대로 더해준다.

해답 (model solution_2)

def roman_to_num(s):
    if not s:
        return 0
    if numbers.get(s[:2]):
        return numbers.get(s[:2]) + roman_to_num(s[2:])
    return  numbers.get(s[:1]) + roman_to_num(s[1:])

(Bonus)

Number to Roman (300 -> MMM)

def num_to_roman(number):
	result = ""
	ints = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	roms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
	for i in range(len(ints)):
		start = number // ints[i]
		result += roms[i] * start
		number -= ints[i] * start
	return result
  • result는 빈 문자열로 시작하여, 계산 후에 리턴할 숫자를 넣는다.
  • 로마 숫자의 예외들을 roms 리스트에, 그에 대응하는 숫자들을 ints 리스트에 순서대로 나열했다. 큰 숫자부터 차례대로 나누어 갈것이므로 큰 수부터 리스트에 넣었다.
  • for문은 ints의 길이를 range 로 지정하여, 한 숫자씩 차례대로 더해가도록 처리했다.
    • start값은 인덱스가 늘때마다 number에서 ints의 각 인덱스 값을 나눈 수로 업데이트 된다. 2017이 주어진 경우, 2017 // 1000 = 2가 지정된다.
    • result값은 roms의 해당 인덱스 값을 start값만큼 곱한 값이 된다. 2017의 경우, M *2 = MM.
    • 이미 계산이 끝난 자리수는 number에서 빼준다. 2017의 경우, 2017-1000*2 = 17이 다음 number로 지정된다.
profile
🔰

0개의 댓글