504. Base 7 (풀이 + 해석)

의역: 정수를 7진법으로 바꾼 문자열을 반환해라

(주의점: 실제 진법에서 음수는 보수로 처리하는데 해당 문제에서는 단순히 앞에 - 붙인 걸로 음수를 처리 함) 

 

풀이:

재귀 함수 사용

(기억해야 할 내용 재귀는 스택과 같이 제일 먼저 호출한 내용을 제일 마지막으로 처리한다.) 

즉 7^0 부터 나누는 것을 처음으로 호출하고 7^i 까지 나누는 걸 호출 한다면

7^i 부터 처리하고 7^0을 마지막으로 처리한다. 

class Solution {
    // 시간 복잡도 O(log7 n) 공간 복잡도 O(1)
    private StringBuilder ans = new StringBuilder();
    private int recusiveNum;
    private void helper(int i){
        int divisor = (int)Math.pow(7,i);
        if(recusiveNum<divisor)
            return;
        helper(i+1);
        int highDigit = recusiveNum/divisor;
        recusiveNum %= Math.pow(7,i);
        ans.append(highDigit);
    }
    public String convertToBase7(int num) {
        if(num==0) return "0";
        recusiveNum = Math.abs(num);
        helper(0);
        if(num<0)
            ans.insert(0,"-");
        return ans.toString();
    }
}

최적화 

class Solution {
    // 시간 복잡도 O(log7 n) 공간 복잡도 O(1)
    public String convertToBase7Otimal(int num){
        if(num<0)
            return "-"+convertToBase7Otimal(-num);
        if(num<7)
            return num+"";
        return convertToBase7Otimal(num/7)+num%7;
    }
}

메모: 재귀는 쉽게 생각하고 간결하게 짜야 한다.