프로그래머스 124 나라의 숫자 :: 돼지개발자

출저 : https://programmers.co.kr/learn/courses/30/lessons/12899

"자리수와 시작 숫자를 구해서 그 지점에서부터 탐색"

구해야 하는 자리수와 시작 숫자를 알고 나서 그 지점부터 탐색하여 탐색 범위를 확 줄여서 시작한다. 

	startWith= 1	startWith= 2	startWith= 4
length = 1	1 (1)	1 (2)	1 (4)
length = 2	3 (11,12,14)	3 (21,22,24)	3 (...)
length = 3	9 (...)	9 (...)	9 (...)

위와 같이 검색하면 내가 탐색해야 할 지점을 알 수 있다. 만약 여러 개의 테스트가 주어진다면 이 값을 배열로 저장하는 것도 좋을 듯 하지만 위 문제에서는 필요없어 매번 for문을 돌아서 아래 정보를 찾았다.

처음에 String return 하라고 하길래 바보같이 String 을 파라미터로 주어서 계속 String을 생성해 주었더니 시간초과 몇개가 나와 long으로 변경했다. 

startWith 로 시작하는 length 자리 숫자들 중 k 번째 수.

static int nth;
static int length = 1;
static int cnt;
static boolean find;
static String res;
 
public static String solution(int n) {
 
    long[] map = {1,2,4};    
    int sum = 0;
    int w = 1;
    int start = 0;
    nth = 0;
    length = 1;
    find = false;
    res = "";
    cnt = 0;
    
    loop : while(true) {
        for (int i = 0; i < 3; i++) {
            sum += w;
            if(sum >= n) {
                sum -= w;
                start = i;
                break loop;
            }
        }
        w *=3 ;
        length++;
    }
    nth = n-sum;
    
 
    solve(1,map[start]);
    return res;
}
 
static void solve(int len, long val) {
    
    if(find) return;
    
    if(length == len) {
        if(++cnt == nth) {
            find = true;
            res = String.valueOf(val);
        }
        return ;
    }
    
    solve(len+1,(val*10)+1);
    solve(len+1,(val*10)+2);
    solve(len+1,(val*10)+4);
}