[240415] 알고리즘 리부트 49일차 - 프로그래머스 124 나라의 숫자 자바

10진법의 수를 3진법으로 바꾸며 나머지는 진법의 수로 몫은 0이 될 때까지 다시 나누는 몫으로  처리하여 구한다. 기존 3진법의 0,1,2 대신 1,2,4를 쓰는 방식의 풀이이다.

import java.util.*;

class Solution {
    
    public String solution(int n) { 
        
        StringBuilder sb = new StringBuilder();
        
        while(n > 0){
            int remainder = n % 3;
            
            if(remainder == 0) 
                sb.insert(0, "4");
            else if(remainder == 1) 
                sb.insert(0, "1");
            else if(remainder == 2) 
                sb.insert(0, "2");
            
            n = (n - 1) / 3;
        }
        
        return sb.toString();
    }  
}

아래는 정확성 테스트에서는 다 맞으나 효율성 테스트에서는 시간 초과가 발생하는 코드이다. 진법을 사용하지 않고 처리했을 때의 풀이방식이다.

import java.util.*;

class Solution {
    public static Deque<Long> qu;
    public static int[] arr = {1,2,4};
    public String solution(int n) {    
        
        qu = new ArrayDeque<>();        
        StringBuilder sb = new StringBuilder();
        
        int cnt = 0;
        
        if(n == 1) return "1";
        else if(n == 2) return "2";
        else if(n == 3) return "4";
        
        qu.offer(1L);
        qu.offer(2L);
        qu.offer(4L);   
        
        cnt = 3;
        
        long thisNum = 0L;
        
        while(true){
            
            thisNum = qu.poll();                   
            
            for(int i = 0; i< arr.length; i++){
                
                sb.setLength(0);

                long newNum = Long.parseLong(sb.append(thisNum).append(arr[i]).toString());
                qu.offer(newNum);
                
                cnt++;
                
                if(cnt == n) return Long.toString(newNum);
            }       
            
        }
    }
}