BOJ 14915 진수변환기

진수 변환기

문제

정수 m, n을 입력 받아, 10진수 m을 n진수로 바꾸어 출력하는 프로그램을 작성하시오.

입력

첫 줄에서 정수 m, n을 입력 받는다. (0 ≤ m ≤ 1,000,000, 2 ≤ n ≤ 16)

출력

변환한 n진수의 수를 출력한다. 11~16 진수의 경우 10 이상의 수는 A~F 문자를 사용한다.
예를 들어, 10은 A, 11은 B, 12는 C, 13은 D, 14는 E, 15는 F를 사용한다.

예제 입력

8 2

15 4

248 16

예제 출력

1000

33

F8

풀이

처음에는 파이썬 내부에 있는 int, oct, bin, hex같은 함수를 이용하려 했었다.
int함수는 str이나 float을 정수형데이터로 변환해주는 함수다.
int(248, 16)과 같이 사용했는데 16진법의 수로 변환되는 것이 아니라
두번째 인자값인 base는 첫번째 인자인 x가 어떤 진법의 수인지 알려주는 인자였다.
int함수에 관해서는 여기를 참조하면 자세하게 볼 수 있다.
따라서 몫, 나머지를 이용해서 진법변환 함수를 구현하기로 했다.

코드 구현부

def convert(number, base):
    CHARS = "0123456789ABCDEF"
    i, j = divmod(number, base)

    if i == 0:
        return CHARS[j]

    else:
        return convert(i, base) + CHARS[j]


M, N = map(int, input().split())
print(convert(M, N))

divmod함수를 이용해 나머지와 몫을 계산해 사용했다.

divmod함수의 정의는 아래와 같다.

def divmod(a: _N2, b: _N2)
Return the tuple (x//y, x%y). Invariant: div*y + mod == x.

몫과 나머지를 튜플 데이터 타입으로 반환하는 함수다.
몫을 i에 나머지를 j에 저장한 후 몫이 0인 경우 CHARS문자열에서
j번째 문자열을 반환하고 몫이 0이 아닌경우 재귀함수를 이용해 몫이 0이 될때까지
모든 자리수를 계산해 문자열을 더하는 방식을 사용했다.

예제

문제의 3번째 테스트케이스인 M = 248, N = 16을 예제로 들어보겠다.

몫이 0이 되는 것을 재귀함수의 탈출 조건이다.
위의 그림처럼 divmod함수를 사용하면서 몫이 0이될 때까지 재귀함수를 진행한다.
몫이 0이 되지 않으면 convert함수에 몫을 넣어 재귀호출하고 나머지는 CHARS에서
해당 진법에 해당하는 문자열을 가져와 convert함수의 반환값과 더해준다.
재귀를 탈출하는 몫이 0인 함수의 반환값이 변환된 수의 가장 앞자리다.
역순으로 돌아오면서 앞자리부터 문자열을 더해가면서 결과를 반환한다.

결과

재귀함수를 이용해 간단하게 진법변환 함수를 구현할 수 있었다.

간단한 재귀함수이긴하지만 재귀호출 과정을 직접 그려보면서 이해하는 것도 좋을 것 같다.

✅ 코드는 [여기]에서 확인할 수 있다.