[문자열 처리] 불길한 수열

문제

4, 13, 413, 134와 같이 숫자가 13과 4를 이용해서 만들 수 있는 수를 불길한 수라고 한다. 그리고 불길한 수가 오름차순으로 나열된 수열을 불길한 수열이라고 한다. 예를 들어 불길한 수열은 다음과 같이 나열될 수 있다.

 

ex) S = {4, 13, 44, 134, 413, 444, 1313......}

 

n이 매개변수로 주어질 때, 불길한 수열에서 n번째 불길한 수를 구하시오.

 

 

 

 

풀이

이 문제는 ArrayList를 Queue처럼 사용하여 풀었다. 처음에 큐에 4와 13을 넣어주고, dequeue 횟수가 주어진 n보다 작을 때까지 제일 앞의 요소를 꺼내어 4와 13을 뒤에 추가하여 리스트에 넣어주었다.

n개가 리스트에 저장이 되면 오름차순으로 정렬을 해준 후, 해당 위치의 값을 리스트에서 뽑아서 리턴해주는 방식으로 구현했다. 

 

 

 

import java.util.*;
 
public class Main {
    static ArrayList<Integer> tmp = new ArrayList<Integer>();//큐 처럼 사용
    static ArrayList<Integer> list = new ArrayList<Integer>();//불길한 수 수열
    
    static long get_unlucky_number(int n) {
        long answer = 0;
        int cnt=0;
        tmp.add(4);
        tmp.add(13);
        
        while(true) {
            if(cnt > n) {
                break;
            }
            int num = tmp.remove(0);
            tmp.add(Integer.parseInt(num+"4"));
            tmp.add(Integer.parseInt(num+"13"));
            list.add(num);
            cnt++;
        }
        Collections.sort(list);//정렬
        return list.get(n-1);
    }
    public static void main(String[] args) {
        System.out.println(get_unlucky_number(4));
    }
}