[자바] 백준 1422 - 숫자의 신 (java)

 문제 : boj1422

---

 

필요 알고리즘 개념

• 정렬, 그리디
  
  • 그리디로 접근해서 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 K==N 이라고 생각해보자. 즉, 모든 숫자를 1번씩 배치해서 가장 큰 수를 만들어야 한다. 어떤 수를 먼저 배치하는게 이득일까? 어차피 만들어진 수의 자리수는 K개의 숫자들의 자리수의 합과 동일하다. 따라서 단순히 큰 수가 먼저오는건 의미가 없다. 예를들어 1과 100 중에 크다고 100을 앞에 두면 1001이지만, 1을 앞에둔 1100이 답이다.

 

  어떤 수가 더 먼저 오는게 이득인지 확인할 아주 간단한 방법이 있다. 직접 붙여보면 된다. 즉 A와 B 중 누가 먼저 와야할지 정할 때, A뒤에 B를 붙인 것과 B 뒤에 A를 붙인걸 비교해주면 된다. 그럼 이 정렬 규칙대로 정렬하면 되므로 K==N일 때는 해결되었다.

Arrays.sort(arr, (s1, s2) -> (s2+s1).compareTo(s1+s2));

 

  다음으로 K<N 일 때를 생각해보자. 이 경우엔 결국 여러번 배치했을 때 도움이 되는 녀석을 N-K번 배치하면 될것이다. 이 경우엔 위와 좀 다르게, 뭘 여러번 두냐에 따라 자리수가 달라진다. 1자리 숫자가 아니므로, 당연히 자리수가 가장 큰 녀석을 배치하는게 항상 이득이다. 예를들어 9, 100이 있다고 해보자. K=2이다. 이 때 N=2라면 1009가 아니라 9100이 답이다. 하지만 N=3이라면, 기존 이득이었던 9 대신 100을 여러번 배치한 9100100이 이득이다. 99100에 비해 자리수가 크기 때문이다. 그러므로 우선 입력으로 주어진 입력값들 중 자리수가 큰 값을 판별할 수 있어야 한다. 자리수가 큰 값이 여러개라면 어떻게 해야할까? 자리수가 가장 큰 값들 중에 앞에 두었을 때 가장 이득인 녀석을 N-K번 배치하면 된다.

Arrays.sort(arr, (s1, s2) -> (s2+s1).compareTo(s1+s2));	// 어떤걸 앞에 두는게 이득일지에 따라 정렬

StringBuilder sb = new StringBuilder();
boolean maxChk = false;
for (int i = 0; i < k; i++) {
    if (!maxChk && arr[i].length()==maxLen) {	// 가장 긴 자리수인 녀석들 중 가장 앞에 두는게 이득인 녀석을
        maxChk = true;
        for (int j = 0; j < n-k+1; j++)	// N-K번 출력
            sb.append(arr[i]);
    } else {
        sb.append(arr[i]);	// 나머지는 1번씩 출력
    }
}

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        String[] arr = new String[k];
        int maxLen = 0;
        for (int i = 0; i < k; i++) {
            arr[i] = br.readLine();
            maxLen = Math.max(maxLen, arr[i].length());
        }

        Arrays.sort(arr, (s1, s2) -> (s2+s1).compareTo(s1+s2));

        StringBuilder sb = new StringBuilder();
        boolean maxChk = false;
        for (int i = 0; i < k; i++) {
            if (!maxChk && arr[i].length()==maxLen) {
                maxChk = true;
                for (int j = 0; j < n-k+1; j++)
                    sb.append(arr[i]);
            } else {
                sb.append(arr[i]);
            }
        }
        System.out.println(sb);
    }
}