👨💻 문제
✍️ 풀이 과정
해당 문제는 평소에 풀던 다른 문제들에 비해 난이도가 있는만큼 문제를 풀기 전,
푸는 과정의 생각들을 모두 정리하며 문제를 풀었다.
✍️ 풀이 과정에서는 틀린 추측과 과정이 포함되어 있다.
옳은 말만 보고 싶다면 아래의 ✍️ 풀이를 보자.
🤔 생각
N개 중에 K개를 중복해서 뽑되, 사용하지 않는 숫자가 없어야 한다고 한다.
이 말은 그냥 N개 다 써버리고 K-N개 만큼 원하는 걸 더 쓰라는 말이다.
단순히 숫자 정렬해서
일단 모든 숫자를 정렬한 순서대로 나열하고
가장 큰 숫자를 앞에 다 붙이면 안 되나?
input
3 4
1
10
100
output
100100101
answer
110100100안 된다.
하지만 일단 모든 숫자를 정렬한 순서대로 나열한다는 것은 무조건 맞다고 생각한다.
일단 정렬에 대해 생각해보자.
🗃️ 정렬
위 반례의 경우 100보다 1과 10이 앞으로 가야 숫자가 더 커진다.
단순히 숫자의 크기로 정렬해선 안 된다.
그렇다면 숫자가 아닌 문자열로 다룬다.
1. 길이에 관계없이 문자열을 인덱스로 모두 비교했을 때 먼저 큰 수가 나오면 우선순위가 높다.
2. 모두 같은데 길이가 다른 숫자
ex) 10, 1 -> 1, 10
ex) 19, 1 -> 19, 1위 예시를 생각하면 단순히 길거나 짧은 게 우선순위가 높아지면 안 될 것 같다.
각 숫자들의 우선순위를 비교하는 데에는
2개의 숫자를 앞이나 뒤로 한 번씩 붙여보고 비교하면 될 것 같다.
하지만 직접 붙여 비교한다면 메모리 및 시간 낭비가 과할 것이다.
심지어 숫자 갯수가 10억개이다.
그럼 직접 붙이지 않고 붙였다고 생각하고 인덱스로 비교를 해보자
🧪 잔여 횟수
정렬은 위까지 하면 될 것 같다.
이제 K - N만큼 중복된 숫자를 더 뽑아 이어 붙이면 끝난다.
숫자는 길면 길수록 크다.
그러니 그냥 가장 큰 숫자를 쓰면 될 듯 하다.
문제는 앞에 붙이냐, 뒤에 붙이냐인데,
이 경우, 아까 구상한 비교 연산을 현재까지 만들어놓은 문자열에 적용하면 될 듯 하다.
가장 큰 숫자가 현재까지 만들어놓은 문자열보다 크다면 앞에다 K - N개 붙여버리고,
작다면 뒤에다 K - N개 붙여버린다.
👨💻 구현
정렬
우선 정렬부터 구현했다.
private static class NumberStringComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
int o1Length = o1.length();
int o2Length = o2.length();
int length = o1Length + o2Length;
for (int i=0; i<length; i++) {
char o1Value = (i < o1Length) ? o1.charAt(i) : o2.charAt(i - o1Length);
char o2Value = (i < o2Length) ? o2.charAt(i) : o1.charAt(i - o2Length);
if (o1Value != o2Value) {
// 큰 순서
return o2Value - o1Value;
}
}
return 0;
}
}
public static void main(String[] args) throws IOException {
input();
// 정렬
Arrays.sort(numberStrings, new NumberStringComparator());
// 모든 숫자 사용
StringBuilder sb = new StringBuilder();
for (int i=0; i<N; i++) {
sb.append(numberStrings[i]);
sb.append(' ');
}
System.out.println(sb);
}input
4 4
213
21
22
2
output
22 2 213 21 기대했던대로 잘 동작하는 것을 확인할 수 있다.
비교 연산을 이후에 재사용해야 하기 때문에 Comparator를 만들었는데
Comparator 클래스는 잘 안 쓰던 것인데 IDE가 없었다면 쓰지 못 했을 것 같다.
이번 기회에 잘 알아두어야겠다.
가장 큰 수
// 가장 큰 수
String largestNumberString = getLargestNumberString();
System.out.println(largestNumberString);
}
...
private static String getLargestNumberString() {
int maxValue = Integer.MIN_VALUE;
String result = "";
for (String numberString : numberStrings) {
if (result.length() > numberString.length()) {
continue;
}
if (result.length() < numberString.length()) {
result = numberString;
maxValue = Integer.parseInt(numberString);
continue;
}
// result.length() == numberString.length()
int numberStringIntValue = Integer.parseInt(numberString);
if (maxValue < numberStringIntValue) {
result = numberString;
maxValue = numberStringIntValue;
}
}
return result;
}가장 큰 수를 구하기 위해서,
모든 문자열을 숫자로 변환하고 비교하는 방법이 간단하다.
하지만 문자열의 길이를 비교한 후, 길이가 같을 때만 숫자로 바꾸어 비교하는 것이 더 효율적이다.
input
4 4
98745
945186
1223546
2156489
output
2156489잘 된다.
비교 후 이어붙이기
// 모든 숫자 사용 , 가장 큰 수 비교
String usedAllNumberStringOnce = sb1.toString();
boolean largestToFront = numberStringComparator.compare(usedAllNumberStringOnce, largestNumberString) > 0;
// 가장 큰 수 K - N 반복
StringBuilder sb2 = new StringBuilder();
for (int i=0; i<K-N; i++) {
sb2.append(largestNumberString);
}
String repeatedLargestNumberString = sb2.toString();
// 붙여서 출력
if (largestToFront) {
System.out.print(repeatedLargestNumberString);
System.out.println(usedAllNumberStringOnce);
}
else {
System.out.print(usedAllNumberStringOnce);
System.out.println(repeatedLargestNumberString);
}
}🛑 반례
틀렸다.
반례를 찾아보았다.
input
3 4
91
222
11
output
9122211222 (91 222 11 222)
answer
9122222211 (91 222 222 11)가장 긴 숫자를 단순히 앞이나 뒤로 붙여서는 안 되는 것이었다.
반례를 보자마자 떠올랐다.
모든 숫자는 한 번씩 사용된다.
가장 큰 숫자가 사용된 자리에 가장 큰 숫자를 K-N번 반복해서 추가로 넣어주면 된다.
그렇다면 가장 큰 숫자와 모든 숫자를 한 번씩 사용하여 이어붙인 문자열을 비교할 필요도 없고,
comparator 클래스도 재사용할 필요가 없다.
public static void main(String[] args) throws IOException {
input();
// 정렬
Arrays.sort(numberStrings, numberStringComparator);
// 가장 큰 수
String largestNumberString = getLargestNumberString();
// 모든 숫자 사용
StringBuilder sb = new StringBuilder();
for (int i=0; i<N; i++) {
sb.append(numberStrings[i]);
// 가장 큰 수라면 더 집어넣는다.
if (numberStrings[i] == largestNumberString) {
sb.append(numberStrings[i].repeat(K - N));
}
}
System.out.println(sb);
}오히려 코드가 훨씬 간단하고 짧아졌다.
✍️ 풀이
🤔 방법
N개 중에 K개를 중복해서 뽑되, 사용하지 않는 숫자가 없어야 한다고 한다.
이 말은 그냥 N개 다 써버리고 K-N개 만큼 원하는 걸 더 쓰라는 말이다.
가장 큰 숫자를 만들기 위해선 당연히 정렬을 해야 한다.
일단 모든 숫자를 적절한 기준으로 정렬하여 순서대로 나열한 후,
가장 큰 숫자 를 K-N회 만큼 적절한 위치에 삽입하면 된다.
🗃️ 정렬
단순히 숫자의 크기로 정렬해선 안 된다.
그렇기에 숫자가 아닌 문자열로 다룬다.
1. 길이에 관계없이 문자열을 인덱스로 모두 비교했을 때 먼저 큰 수가 나오면 우선순위가 높다.
2. 모두 같은데 길이가 다른 숫자
ex) 10, 1 -> 1, 10
ex) 19, 1 -> 19, 1위 예시를 보면 단순히 길거나 짧은 게 우선순위가 높아지면 안 된다.
각 숫자들의 우선순위를 비교하기 위해선 2개의 수를 앞뒤로 한 번씩 붙여보고 비교하면 된다.
하지만 직접 붙여 비교한다면 메모리 및 시간 낭비가 과하다.
심지어 숫자 갯수가 10억개이다.
직접 붙이지 않고 붙였다고 생각하고 인덱스로 비교를 한다.
private static void sort() {
Arrays.sort(numberStrings, (String o1, String o2) -> {
int o1Length = o1.length();
int o2Length = o2.length();
int length = o1Length + o2Length;
for (int i=0; i<length; i++) {
char o1Value = (i < o1Length) ? o1.charAt(i) : o2.charAt(i - o1Length);
char o2Value = (i < o2Length) ? o2.charAt(i) : o1.charAt(i - o2Length);
if (o1Value != o2Value) {
// 큰 순서
return o2Value - o1Value;
}
}
return 0;
});
}🧪 잔여 횟수
이제 K - N만큼 중복된 숫자를 더 뽑아 이어 붙이면 끝난다.
숫자는 길면 길수록 크고 크면 클수록 길다.
그러므로 가장 큰 숫자를 찾는다.
이 때 숫자들은 문자열이고 길이가 길 수 있기 때문에, 항상 숫자로 변환하지 않는다.
일단 길이로 비교하고, 길이가 같다면 숫자로 변환하여 비교한다.
private static String getLargestNumberString() {
int maxValue = Integer.MIN_VALUE;
String result = "";
for (String numberString : numberStrings) {
if (result.length() > numberString.length()) {
continue;
}
if (result.length() < numberString.length()) {
result = numberString;
maxValue = Integer.parseInt(numberString);
continue;
}
// result.length() == numberString.length()
int numberStringIntValue = Integer.parseInt(numberString);
if (maxValue < numberStringIntValue) {
result = numberString;
maxValue = numberStringIntValue;
}
}
return result;
}가장 큰 숫자를 찾았다면 해당 숫자를 어디에 넣어야 할지가 관건이다.
우리는 이미 숫자들을 정렬했다.
가장 큰 숫자가 있는 위치에 가장 큰 숫자를 K-N번 추가로 삽입해주면 된다.
실제로 삽입을 하게 된다면 메모리 소모가 크기 때문에 결과를 출력할 때만 추가적으로 넣어서 출력한다.
StringBuilder sb = new StringBuilder();
for (int i=0; i<N; i++) {
sb.append(numberStrings[i]);
// 가장 큰 수라면 더 집어넣는다.
if (numberStrings[i] == largestNumberString) {
sb.append(numberStrings[i].repeat(K - N));
}
}
System.out.println(sb);📄 전체 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N;
private static int K;
private static String[] numberStrings;
public static void main(String[] args) throws IOException {
input();
sort();
String largestNumberString = getLargestNumberString();
// 모든 숫자를 한 번씩 사용
StringBuilder sb = new StringBuilder();
for (int i=0; i<N; i++) {
sb.append(numberStrings[i]);
// 가장 큰 수라면 더 집어넣는다.
if (numberStrings[i] == largestNumberString) {
sb.append(numberStrings[i].repeat(K - N));
}
}
System.out.println(sb);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
numberStrings = new String[N];
for (int i=0; i<N; i++) {
numberStrings[i] = br.readLine();
}
}
private static void sort() {
Arrays.sort(numberStrings, (String o1, String o2) -> {
int o1Length = o1.length();
int o2Length = o2.length();
int length = o1Length + o2Length;
for (int i=0; i<length; i++) {
char o1Value = (i < o1Length) ? o1.charAt(i) : o2.charAt(i - o1Length);
char o2Value = (i < o2Length) ? o2.charAt(i) : o1.charAt(i - o2Length);
if (o1Value != o2Value) {
// 큰 순서
return o2Value - o1Value;
}
}
return 0;
});
}
private static String getLargestNumberString() {
int maxValue = Integer.MIN_VALUE;
String result = "";
for (String numberString : numberStrings) {
if (result.length() > numberString.length()) {
continue;
}
if (result.length() < numberString.length()) {
result = numberString;
maxValue = Integer.parseInt(numberString);
continue;
}
// result.length() == numberString.length()
int numberStringIntValue = Integer.parseInt(numberString);
if (maxValue < numberStringIntValue) {
result = numberString;
maxValue = numberStringIntValue;
}
}
return result;
}
}