[백준] 1422번 숫자의 신 Java

문제 링크

https://www.acmicpc.net/problem/1422

문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

알고리즘: 그리디, 정렬

풀이

이 문제는 (https://velog.io/@shinjy9802/%EB%B0%B1%EC%A4%80-16496%EB%B2%88-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0-Java)와 유사하다. 다른 점은 N번 뽑아야 한다는 것이고 N은 K보다 크거나 같다. 주어진 입력에서 제일 큰 수를 N-K번 list배열에 넣어주고 똑같이 sort 하면 끝이다.

소스 코드

import java.io.*;
import java.util.*;

class NumInfo implements Comparable < NumInfo > {
    long v;
    int pv[];
    public NumInfo(long v, int pv[]) {
        this.v = v;
        this.pv = pv;
    }

    public int compareTo(NumInfo n) {
        int spv[] = this.pv.length <= n.pv.length ? this.pv : n.pv;
        for (int i = 0; i < spv.length; i++) {
            int df = n.pv[i] - this.pv[i];
            if (df > 0) return 1;
            if (df < 0) return -1;
        }
        String tpv = String.valueOf(this.v) + String.valueOf(n.v);
        String npv = String.valueOf(n.v) + String.valueOf(this.v);
        for(int i=0; i<tpv.length(); i++) {
            int tv = tpv.charAt(i) - '0';
            int nv = npv.charAt(i) - '0';
            if(tv > nv) return -1;
            if(tv < nv) return 1;
        }
        return 0;
    }
}

public class Main {
    static int N, K;
    static NumInfo list[];
    static NumInfo max = new NumInfo(-1, new int[0]);
    static StringBuilder sb = new StringBuilder();
    static int insert_ind = -1;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        list = new NumInfo[N];
        for (int i = 0; i < K; i++) {
            String s = br.readLine();
            int pv[] = new int[s.length()];
            for (int j = 0; j < pv.length; j++) {
                pv[j] = s.charAt(j) - '0';
            }
            long v = Long.parseLong(s);
            list[i] = new NumInfo(v, pv);
            if(max.v < v) max = list[i];
        }
        for(int i = K; i<N; i++) {
            list[i] = new NumInfo(max.v, max.pv);
        }
        Arrays.sort(list);
        for (int i = 0; i < N; i++) {
            sb.append(list[i].v);
        }
        System.out.println(sb.toString());
    }
}