[LeetCode] 504. Base 7

504. Base 7

Easy

Given an integer num, return a string of its base 7 representation.

 

Example 1:

Input: num = 100
Output: "202"

Example 2:

Input: num = -7
Output: "-10"

 

Constraints:

• -107 <= num <= 107

---

문제 풀이

• 주어진 숫자를 이진수처럼 칠진수로 만들어 문자열로 리턴하는 문제이다.
• 10진수를 2진수로 변경하는 것처럼 몫과 나머지를 사용하여 문제를 풀 수 있다. 
• 문제 제한은 최악의 경우 10^7이지만 for loop를 하나만 사용하면 되니 O(N)시간안에 풀 수 있다.
• 여기서 두가지 예외처리가 필요하다. 
• 0이 나올경우 간단하게 '0'을 리턴하고, 음수가 등장했을때 플래그 변수를 만들어 저장하여 나중에 음수로 처리한다.  
• 이러한 수학계산을 하기위해서는 기준이되는 숫자로 계속해서 주어진 숫자를 나누면서 계산한다. 
• 0 ~ 6까지의 숫자를 사용할 수 있는데, 7은 0이라고 생각하면 된다. 
• 처음 숫자를 7로 나눈 숫자의 나머지를 정답 끝에 넣는다. 
• 그리고 몫을 다시 7로 나누어 반복하는 방법으로 문제를 푼다.
• 쉽게 10진수를 2진수로 만드는 예로 설명해보면, 10을 2진수로 만들어보자.
• 10은 2진수 1010 이다. 숫자위치는 순서대로 8421의 의미를 가지고 있다. 
• 10을 2로 나누면 0으로 나누어 떨어지기 때문에 0을 맨 뒷자리에 넣는다. 
• 10을 2로 나눈 5를 2로 나누면 1이 남기 때문에 1을 0 앞에 넣어 10을 만든다.
• 5를 2로 나눈 2를 2로 나누면 0이 남아서 10 앞에 0을 넣어 010을 만든다.
• 2를 2로 나눈 1을 2로 나누면 1이 남아서 010 앞에 1을 넣어 1010을 만든다.
• 7진수도 위처럼 계산하여 정답을 만들면 된다. 

소스 코드

class Solution:
    def convertToBase7(self, num: int) -> str:
        # if num is zero, return '0'
        if num == 0: 
            return '0'
        # handle with negative number
        flag = 1
        ans = ''
        if num < 0:
            num *= -1
            flag = 0
        while num:
            # divide, modular
            divided = num // 7
            modular = num % 7
            ans += str(modular)
            num = divided
        # reverse string
        ans = ans[::-1]
        return str(ans) if flag else str('-') + str(ans)