[백준 1422] 숫자의 신

문제 요약

입력으로 K개의 숫자가 주어진다. 이때 각 숫자의 범위는 1,000,000,000보다 작거나 같은 자연수이다.

이때 주어진 숫자들을 골라 앞, 뒤로 붙여서 만들 수 있는 숫자 중 가장 큰 숫자는 무엇인지 구하라.

단, 입력으로 주어진 K개의 숫자는 반드시 한 번씩 들어가야 하고, 여러 번 쓸 수 있다.

 

접근 과정

처음에 문제를 읽었을 때

문제 자체는 짧고 명료하기에 쉽게 이해했지만

구현에 대한 아이디어를 떠올리느라 매우 깊은 고민에 빠지게 됐다.

 

첫 번째로 든 생각

"그냥 큰 숫자만 앞에 가면 되는 거 아니야?"

 

반례

K=2일 때

1007, 7 이 주어졌다면

1007이 크다고 해서

1007+7 = 10077로 만든 건 정답이 될 수 없다.

7+1007을 하면 71007이 더 크기 때문이다.

 

해법

K개로 들어오는 각각의 숫자들은 10억이 넘기 때문에

붙이는 과정에서 무조건 int나 long로 표현이 불가하니 String으로 처리한다.

들어오는 K개의 숫자들을 정렬해보고 싶은데 각각을 서로 앞, 뒤로 붙였을 때 더 큰 숫자가 앞에 가도록 하고 싶다.

이때 자바의 Comparator를 사용하여 앞으로 붙여보고 뒤로 붙여봤을 때 더 큰 숫자를 기준으로 정렬 기준을 세워주면 되겠다. 

 

즉, 

위에 예시로 든 케이스에서

7,1007을 String으로 비교했을 때 

자바의 Comparator를 활용하면 71007과 10077을 비교할 수 있게 된다. 

 

 

여기서 compare 메서드의 파라미터

o1 = 7

o2 = 1007일 때 ,

 

o1+o2 = 71007

o2+o1 = 10077 

o = o1+o2  (o = 71007)

 

-o.compareTo(o2+o1)을 통해 ( 앞의 음수 - 는 내림차순을 뜻한다.)

즉, 71007과 10077중 누가 더 크냐라는 기준을 Comparator에 정해준다.

        Arrays.sort(numlist,new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String o=o1+o2;
                return -o.compareTo(o2+o1);
            }
        });

 

이에 대한 결과로

71007과 10077 중 71007이 더 크므로

o1 = 7 이 

o2 = 1007보다 사전 순으로 더 앞에 위치하게 된다.

 

실제로 정렬된 결과를 보면

K = 3, N = 3이고

 

K개의 숫자로 입력이 다음과 같이 들어올 때 

3 3

1007

9

7

 

위와 같은 정렬 기준을 두고 정렬을 하면 다음과 같은 결과를 얻을 수 있다.

 

 

 

 

위와 같이 K개의 숫자를 정렬한 결과를 살펴보면

1007,9,7로 만들 수 있는 숫자는 971007 임을 알 수 있다.

 

K개의 숫자는 각각 무조건 한 번씩은 나와야 하는 것이고

 

여기서 N이 K보다 크다면 (N-K) 개를 골라서 위 숫자 971007의 적절한 자리에 붙여야 하는데

이때 9가 가장 크니 가장 앞에 위치시키고 1007이 가장 작으니 가장 뒤에 위치시킨다.

이때 중간에 끼어들어야 하는 수는 자릿수가 가장 크면서 가장 큰 숫자를 넣어주면 된다.

즉, 입력을 받을 때 9,7,1007중 자릿수가 가장 크면서 가장 큰 숫자는 1007이고

 

위와같이 앞, 뒤로 붙이는 정렬을 통해 

971007을 만든 후 

N=5 라면

(N-K)는 2이니

두 개를 더 붙이는 과정에서 자릿수가 가장 크면서 가장 큰 숫자인 1007을 뒤에 붙여주면 되는 것이다.

즉, 

971007+1007+1007 = 97100710071007이 현재 예제에서 만들 수 있는 가장 큰 숫자가 되는 것이다.

        boolean flag=false;
        for(int i=0;i<K;i++) {
            answer+=numlist[i];
            if(max==Integer.parseInt(numlist[i]) && flag==false){
                flag = true;
                for(int j=0;j<(N-K);j++) {
                    answer+=numlist[i];
                }
            }
        }

 

 

따라서 이 문제에서 해야 하는 두 가지 작업

 

1. 숫자를 String으로 둔 뒤 앞으로 붙이고 뒤로 붙여서 더 큰 숫자가 앞에 위치하도록 정렬 후 K개의 숫자를 우선적으로 나열

2. 입력받을 때 가장 크고 가장 자릿수가 큰 숫자를 Max값으로 기억해둔 뒤 나열된 K개의 숫자에서 Max값과 같은 위치에서 (N-K)만큼 이어 붙이기, 단, K개의 숫자들 중 중복되는 수가 있다는 문제의 조건에 의해 Max값을 한 번만 찾아 (N-K) 개만큼 이어 붙여야 한다.

 

풀이 코드

public class 숫자의신 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N,K;
    static int max;
    static String[] numlist;
    static String answer ="";
    public static void main(String[] args) throws IOException {
        setData();
        getMaxValue();
        System.out.println(answer);
    }
    private static void setData() throws IOException {
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        numlist = new String[K];
        for(int i=0;i<K;i++) {
            String sv = br.readLine();
            int value = Integer.parseInt(sv);
            /*
             * 입력받으며 K개의 숫자들 중 가장 큰 숫자를 max에 저장
             */
            if(max<value) max = value;
            numlist[i] = sv;
        }
        
        /*
         * 두 String 숫자를 앞으로 분인것과 뒤로 붙인것을 비교하는 정렬 기준을 세운 뒤 정렬 
         */
        //Collection Sort에서 Array Sort로 변경
        Arrays.sort(numlist,new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String o=o1+o2;
                return -o.compareTo(o2+o1);
            }
        });
    }
 
    private static void getMaxValue() { 
        
        /*
         * 입력받을 때 구한 K개의 숫자중 가장 큰 숫자가 자리수도 크고(붙이게되면 가장 길어지고) 가장 큰 숫자이므로 
         * 해당 max값에 해당하는 숫자가 나타난 위치부터 복사해서 이어 붙인다.
         * 여기서 boolean을 둔 이유는
         * 문제에서 숫자가 중복으로 들어올 수 있다는 조건 떄문에
         * K개의 숫자 중 2222,2222로 중복으로 들어온다면 또 다시 이어붙이게 되니 이를 방지하기 위함이다. 
         */
        boolean flag=false;
        for(int i=0;i<K;i++) {
            answer+=numlist[i];
            if(max==Integer.parseInt(numlist[i]) && flag==false){
                flag = true;
                for(int j=0;j<(N-K);j++) {
                    answer+=numlist[i];
                }
            }
        }
    }
}

 

https://github.com/Jangsukwoo/Algorithm/blob/master/Algo/src/BAEKJOON/%EC%88%AB%EC%9E%90%EC%9D%98%EC%8B%A0.java

Jangsukwoo/Algorithm