https://www.acmicpc.net/problem/1422
1422번: 숫자의 신
첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.
www.acmicpc.net
숫자 K개중에 N개를 뽑고 그수를 붙여서 만들수 있는 가장 큰 수를 만드는 문제이다. (단 N>=K이다.)
숫자 K개는 무조건 한번 이상은 써야하고 (N-K)만큼은 중복되서 사용해야한다.
중복의 횟수에 제한이 없기 때문에 가장 크게 만드는 수를 계속 중복해서 사용해야 가장 큰 수가 나온다.
가장 크게 만드는 수는
1. 가장 길이가 긴 숫자
2. 길이가 같다면 더 큰 숫자이다.
예를들어
277
9
3333
9979
이 4개 수중에 3333, 9979가 가장 길고 9979가 더 크므로 가장 길게 만드는 숫자는 9979이다.
이 중복할 숫자를 N-K만큼 배열에 넣어준다.
이제 중복할 숫자를 포함한 N개의 숫자를 다음과 정렬해준다.
9 , 77를 비교한다면
977 > 779 이므로 9가 77보다 큰 문자열이다.
997 , 9를 비교할떄
9979 < 9997이므로 9가 997보다 큰 문자열이다.
즉 두 숫자 s1,s2 가 있을때 s1.concat(s2)와 s2.concat(s1)을 비교해준다.
(숫자가 1000000000 인 수 (문자열로 환산시 길이 10이하) 만 입력되므로 concat을 많이 하더라도 거의 시간적으로 손해보는 시간이 없다.)
이렇게 출력된 수들을 끝에서부터 하나씩 출력해주면된다.
PS) 예제가 매우 빈약했기때문에 반례를 최대한 많이 찾아줬던게 도움이 많이 됐다.
import java.util.*;
import java.io.*;
public class Main {
public static class MyScanner {
BufferedReader bf;
StringTokenizer st;
MyScanner() {
bf = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(bf.readLine());
} catch (Exception e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
public static void main(String[] args) {
MyScanner sc = new MyScanner();
int K = sc.nextInt();
int N = sc.nextInt();
ArrayList<String> arr = new ArrayList<String>();
ArrayList<String> ans = new ArrayList<String>();
for (int i = 0; i < K; i++) {
arr.add(sc.next());
ans.add(arr.get(i));
}
Collections.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() != o2.length())
return o1.length() - o2.length();
else
return o1.compareTo(o2);
}
});
for (int i = 0; i < N - K; i++) {
ans.add(arr.get(K - 1));
}
Collections.sort(ans, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.concat(o2).compareTo(o2.concat(o1));
}
});
for (int i = N - 1; i >= 0; i--) {
System.out.print(ans.get(i));
}
}
}