[백준 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에 정해준다.
|
1
2
3
4
5
6
7
|
Arrays.sort(numlist,new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String o=o1+o2;
return -o.compareTo(o2+o1);
}
});
|
cs |
이에 대한 결과로
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이 현재 예제에서 만들 수 있는 가장 큰 숫자가 되는 것이다.
|
1
2
3
4
5
6
7
8
9
10
|
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];
}
}
}
|
cs |
따라서 이 문제에서 해야 하는 두 가지 작업
1. 숫자를 String으로 둔 뒤 앞으로 붙이고 뒤로 붙여서 더 큰 숫자가 앞에 위치하도록 정렬 후 K개의 숫자를 우선적으로 나열
2. 입력받을 때 가장 크고 가장 자릿수가 큰 숫자를 Max값으로 기억해둔 뒤 나열된 K개의 숫자에서 Max값과 같은 위치에서 (N-K)만큼 이어 붙이기, 단, K개의 숫자들 중 중복되는 수가 있다는 문제의 조건에 의해 Max값을 한 번만 찾아 (N-K) 개만큼 이어 붙여야 한다.
풀이 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
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];
}
}
}
}
}
|
cs |
Jangsukwoo/Algorithm
Contribute to Jangsukwoo/Algorithm development by creating an account on GitHub.
github.com