[python] 백준 알고리즘 2537번: k진수 정수의 자릿수 나누기 - python에서 n진법으로 숫자 바꾸기

https://www.acmicpc.net/problem/25371

 

---

 

k진수 정수의 자릿수 나누기

문제

양의 정수 n과 k가 주어진다. n을 k진수로 변환한 수를 a라고 하자. a의 각 자릿수를 0을 기준으로 나눈 결과를 집합 b라고 하자. 0이 연속으로 나와서 공백이 생기는 경우는 집합 b에 포함되지 않는다. 집합 b에 있는 수의 합을 k진수로 출력하자. 예를 들어, n = 19, k = 2이면 a = 100112, b = {1, 11}, 1 + 11 = 12, 12 = 11002이므로 1100을 출력한다.

입력

첫 번째 줄에 양의 정수 n과 k가 공백을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 집합 b에 있는 수의 합을 k진수로 출력한다.

제한

• 1 ≤ n ≤ 1,000,000
• 2 ≤ k ≤ 10

예제 입력 1 

437674 3

예제 출력 1 

22101

437674를 3진수 변환하면 a = 2110201010113이다.

2110201010113을 0을 기준으로 나누면 b = {211, 2, 1, 1, 11}이다.

b에 있는 수의 합은 211 + 2 + 1 + 1 + 11 = 226이다.

226을 3진수로 변환하면 221013이다.

예제 입력 2 

29 3

예제 출력 2 

10

29를 3진수 변환하면 a = 10023이다.

1002를 0을 기준으로 나누면 b = {1, 2}이다.

b에 있는 수의 합은 1 + 2 = 3이다.

3을 3진수로 변환하면 103이다.

예제 입력 3 

11 3

예제 출력 3 

10

11을 3진수 변환하면 a = 1023이다.

102를 0을 기준으로 나누면 b = {1, 2}이다.

b에 있는 수의 합은 1 + 2 = 3이다.

3을 3진수로 변환하면 103이다.

예제 입력 4 

3 3

예제 출력 4 

1

3을 3진수로 변환하면 a = 103이다.

10을 0을 기준으로 나누면 b = {1}이다.

b에 있는 수의 합은 1이다.

1을 3진수로 변환하면 13이다.

출처

• 문제를 검수한 사람: chansol, jthis, leo020630, pjshwa, tlsdydaud1, wider93
• 문제를 만든 사람: MenOfPassion

알고리즘 분류

• 수학
• 구현

 

---

 풀이

 

사실 int(n,k)가 진수로 변경해주는 줄 알았는데 그런 건 아니어서 직접 함수로 구현해봤다.

 

1. 값의 몫과 나머지를 구한다.
2. 나머지는 리스트에 추가해둔다.
3. 몫을 값으로 만들고 1,2번 과정을 n이 0보다 클 때까지 반복한다.
4. 이후 리스트의 순서가 거꾸로이니 반대로 뒤집고 숫자로 만든다.

그리고 알고리즘 풀이 함수로 만들면 끝~

map에 lambda로 예외사항만 추가해주면 된다. 1002 숫자가 split이 되면 '1', '', '2'처럼 되는 예외사항을 추가해줬다.

# 진수 변경 함수 구현
def to_base(n,k):
    transes = []
    while n > 0:
        transes.append(str(n%k))
        n //= k
    transed_number = ''.join(transes[::-1])
    return int(transed_number)

# 알고리즘 풀이
def kbase_divide(n,k):
    # 타입 변경 후 k진수로 변환
    transed_number = to_base(n,k) 

    # 변환된 수 0을 기준으로 나눠서 리스트로 변환
    split_numbers_by_zero = str(transed_number).split('0')
    
    # 0이 남는 경우가 있음을 확인 lambda 형태로 수식 추가

    # 리스트 안에 값을 정수 형태로 바꾼 뒤 총합
    sum_split_numbers = sum(map(lambda x : int(x) if x != '' else 0 ,split_numbers_by_zero))

    # 다 합친 수를 k진수로 변환함
    transed_split_numbers = to_base(sum_split_numbers, k)

    print(transed_split_numbers)
    
if __name__ == "__main__":
    n, k = map(int,input().split())
    kbase_divide(n,k)