1422 숫자의 신

 

1. 정렬 

 

 

사용하는 방법은,

 

ex)

3=K 5=N

1234

567

89

이렇게 있다고 하자.

 

 

그렇다면 1234 567 89 를 number 배열에 넣은 다음 정렬시킨다.

그 방법은 아래에서 자세히 살펴보자.

 

일단 1234 567 89는 모두 1번씩 사용해야 한다. 그렇다면 이 세가지 숫자들을 어떻게 이어붙어야 가장 큰 숫자를 만들 수 있을까?

 

1) 먼저 1234, 567 을 어떤 순서로 이어붙어야 될까?

1234567 < 5671234

이다.

즉, 1234, 567을 이어붙일때, 567이 1234보다 앞에 와야 더 큰 숫자가 된다.

때문에 number 배열에서 567을 1234보다 앞에 정렬시킨다.

 

2) 1234, 89 정렬

123489 < 891234

이기에, 89가 1234보다 앞에 정렬된다.

 

3) 567, 89 정렬

56789 < 89567 

이기에, 89가 567보다 앞에 정렬된다.

 

 

최종적으로

89, 567, 1234 순으로 number 배열에 정렬된다.

 

때문에,

number[0] = 89, number[1] = 567, number[2] = 1234 

이렇게 저장되도록 한다.

 

이때 아래와 같이 코드를 완성하면 된다.

 

 

	Arrays.sort(number, new Comparator<String>() {
		@Override
		public int compare(String a, String b) {
			String A = a+b;
			String B = b+a;
			
			return -A.compareTo(B);
		}
	});

자세히 살펴보자면, comparator 인터페이스의 compare 메서드를 오버라이드해서 정렬 방법을 설정하는데,

먼저 숫자들을 String 형태로 받는다.

즉, 위의 예인

1234 567 89를 각각 String 형태로 입력받는 것이다.

 

1. 문자열 정렬

=> 만약 숫자를 문자로 받아서 정렬해보면?

 

예를 들어서 20, 12222 를 문자열 String 으로 받아서 내림차순 정렬해보자

 

		String a = Integer.toString(12222);
		String b = Integer.toString(20);
		
		String input [] = new String[2];
		input[0] = a;
		input[1] = b;
		
		Arrays.sort(input, Collections.reverseOrder());
		// 내림차순 정렬
		
		
		System.out.println(input[0]);
		System.out.println(input[1]);

 

아래는 이클립스 실행 결과이다.

즉, 숫자를 문자열 String 으로 입력받아서 내림차순 정렬하면,

맨 앞 숫자가 큰 순서대로 정렬됨.

 

=> 아래 글에서 숫자를 String 형으로 받아서 내림차순 정렬하는 것에 대한 이해도를 높일 수 있다.

 

1234, 567을 정렬시킬 때도 사용했듯이,

먼저 

1234567 로 만들어본다. 또 5671234도 만들어본다.

 

즉, 두 숫자를 이어붙여 본 다음, 더 큰수를 만들 수 있는 567 1234 순으로 내림차순 시켜준다.

코드에서 compare 메서드 리턴에 -를 붙여준 것이, 내림차순을 의미하는 것이다.

 

이에 대해 자세히 설명하자면,

 

<1> comparator 인터페이스의 compare 메서드 

1) 리턴값이 음수 또는 0 => 두개의 객체를 정렬시킬 때 두 객체의 자리가 그대로 유지된다.

2) 리턴값이 양수 => 두 객체의 자리가 변경된다.

 

 

 

예를 들어서

배열 input[0] =2, input[1]=3 을 가지고 정렬해보자.

(compare 메서드에서는 int 형은 정렬이 안되기 때문에, Integer 형태로 저장한 다음 정렬시켜야 한다.)

 

	
	Integer input[] = new Integer[2];
		
	input[0] = 2;
	input[1] = 3;
		
        Arrays.sort(input,new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
               
               // 1)
            	if(a>b) {
            		return 1;
                    
                // 2)    
            	}else if(a<b) {
            		return -1;
                    
                // 3)    
            	}return 0;
            }
        });
		
        
        for(int i=0; i<2;i++) {
       System.out.println(input[i]);
	}

 

 

 

 

compare 메서드에서

1) a>b 이면 1을 리턴하라고 했다. 즉 양수가 리턴되므로 두 객체의 자리가 변경된다.

즉, a>b 상태라면 => 3,2 순서로 정렬되어 있다면

=> 2,3 순서로 정렬해라.

 

2) a<b 이면 -1 을 리턴한다. 즉 음수가 리턴되기 때문에 두 객체의 자리가 유지된다.

즉, a<b 상태라면 => 2,3 순서로 정렬되어 있는 것이고,

=> 2,3 순서 그대로 유지된다.

 

3) 만약 a=b 라면, 0 리턴한다. 즉, 두 객체의 자리가 유지된다.

 

input[0] =2, input[1] = 3, input[2] = 2 인 상태에서 만약 저 방법으로 정렬 시키면,

2 2 3 순서대로 정렬됨을 알 수 있다.

 

input[0] =2 와 input[1] = 3 은 위의 정렬 방법에 따라 이 순서가 맞지만,

input[1] =3, input[2] = 2 는 위의 정렬 방법에 의해 순서가 바뀌게 되어서

=> input[0] = 2, input[1] = 2, input[2] =3 이 된다.

 

이때, input[0] =2, input[1] =2 는 정렬조건에서 a==b 를 만족하기 때문에 

이 순서가 유지된다.

 

 

참고자료 :

1) https://lookingfor.tistory.com/entry/%EC%9E%90%EB%B0%94-%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%B9%84%EA%B5%90-%ED%95%A8%EC%88%98-compare-compareTo

 

2) https://velog.io/@injoon2019/%EC%9E%90%EB%B0%94-Comparator%EC%99%80-Comparable

 

 

<2> compareTo 메서드

 

A.compareTo(B)

 

A: 기준값

B: 비교대상

 

1) 기준값 = 비교대상 

결과 : 0 

 

2) 기준값 < 비교대상

결과 : -1

 

3) 기준값 > 비교대상

결과 : 1

 

	
		Integer a = 2;
		Integer b = 3;
		
		System.out.println(a.compareTo(b));

 아래는 이클립스 실행 결과이다.

 

참고 자료 : https://mine-it-record.tistory.com/133

 

<3> 정리.

 

정렬을 살펴보면 최종적으로 compare 메서드에서 compareTo 메서드로 리턴하고 있다.

특히, compareTo 메서드 앞에 - 를 두었는데,

원래 cmopareTo 메서드는 

 

1) 기준값 = 비교대상

결과 : 0 

 

2) 기준값 < 비교대상

결과 : -1

 

3) 기준값 > 비교대상

결과 : 1

 

이렇게 되는데, -를 붙임으로써,

 

1) 기준값 = 비교대상

결과 : 0 

 

2) 기준값 < 비교대상

결과 : 1

 

3) 기준값 > 비교대상

결과 : -1

 

이 된다.

 

그런데, compare 메서드에서는 

1) 리턴값이 음수 또는 0 => 두개의 객체를 정렬시킬 때 두 객체의 자리가 그대로 유지된다.

2) 리턴값이 양수 => 두 객체의 자리가 변경된다.

 

이렇게 때문에,

1) 기준값 = 비교대상,

2) 기준값 > 비교대상(앞에 있는 수가 뒤에 있는 수보다 크다=> 내림차순)

일 경우는 두 객체의 자리가 유지되고,

 

3) 기준값 < 비교대상(오름차순) 일 경우는 두 객체의 자리가 변경된다. 즉, 내림차순이 됨.

 

=> 즉 내림차순 정렬하라는 의미이다.

 

 

 

<4> 주의할점.

 

위의 글에서 더보기 부분에 String 정렬방법에 대해 설명하였다.

 

즉, 숫자를 String 형으로 입력받은 후 내림차순 정렬을 시키면,

a = 89, b = 567 일때,

89, 567 순서로 정렬된다.

 

그렇다면 조금 헷갈릴 수 있다.

 

위의 예시에서 1234, 567, 89 숫자가 최종적으로

89, 567, 1234 순으로 정렬되게 하려했고,

이때 

compare 메서드를 사용하는 등 복잡하게 정렬을 지정하느니,

 

그냥 쉽게 1234, 567, 89 를 number 배열에 입력한 뒤, 그냥 내림차순하면

89, 567, 1234 라는 결과를 얻지 않나??

 

이 경우는 이렇게 해도 되겠지만, 반례가 있다.

 

문제 예시에 

 

3 4

1

10

100 

 

이 있다.

 

이 경우는 만약 String 형으로 내림차순 정렬하면 100 10 1 이 된다.

 

하지만, 위의 compare 메서드를 이용하면 1 10 100 순서대로 정렬됨을 알 수 있다.

 

 

1) 100과 1을 이어붙여서 큰 수를 얻으려면

1001 이 아니라, 1100이기 때문에

1이 100보다 앞에 오게 되고,

 

2) 10과 1을 이어붙여서 큰 수를 얻으려면

101 이 아니라 110이기 때문에

1이 10보다 앞에 오게 되는 것이다.

 

<5> 최종 결론 

 

ex)

3=K 5=N

1234

567

89

 

이런 예시에서는 

1234, 567, 89 를

89, 567, 1234 순서로 정렬한다음,

이 세가지 숫자로 만들 수 있는 최고의 수는

정렬된 배열에서 인덱스를 증가시키면서 1개씩 이어붙이면 완성된다는 것을 알았다.

즉, number[0] + number[1] + number[2] = 895671234

 

그렇다면, N-K =2 만큼 이 세가지 숫자 중에 더 추가해서 최고로 큰 수를 만들어야 하는데, 어떤수를 추가하면 될까?

 

 

2. N-K 번 이어붙일 숫자는?

 

 

숫자는 보통 길이가 길수록 큰 숫자이다.

100 > 10

 

그리고 길이가 같다면, 더 큰 수가 큰 수이다.

 

123 < 456

 

때문에, 그냥 제일 큰 수를 찾으면 된다.

 

1234, 567, 89에서는 1234가 제일 큰 수이다. 때문에 1234를 N-K = 2 만큼 추가해주면 된다.

 

그렇다면, 2번 더 추가될 1234를 어디에 위치시켜야 할까?

 

우리는 위에서 1234, 567, 89가 있을 때에, 

89 567 1234 순으로 만들면 제일 큰 수가 된다고 했다.

 

때문에 1234 1234 를 추가할 때, 위의 89 567 1234 에서 똑같은 숫자인 1234 뒤에 붙여주면 된다.

즉, 89 567 1234 1234 1234 이렇게 만들면 된다.

 

이미 compare 메서드를 통해서 최고의 수를 만들 수 있는 순서대로 정렬시켜 놓은 것이기 때문이다.

 

그래서 최종 코드에서도 볼 수 있듯이, 입력받는 1234, 567, 89 숫자 중에 제일 큰 1234를 max 변수에 저장시켜 놓는다.

최종 결과를 result 변수에 저장하는데 number 배열에서 인덱스 순서대로 result 변수에 이어붙인다.

result += 89 , result += 567, result+=1234

그런데, N-K = 2 만큼 1234를 result 변수에 붙일 수 있도록 while 문을 만들었다.

 

 

3. 최종 코드

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;


public class Main {
	
	public static void main(String[] args) throws IOException {
	
	
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	int K = Integer.parseInt(st.nextToken());
	int N = Integer.parseInt(st.nextToken());
	
	String number [] = new String [K];
	int max = 0;
	
	
	for(int i=0; i<K; i++) {
		number[i] = br.readLine();
		
		if(max<Integer.parseInt(number[i])) {
			max = Integer.parseInt(number[i]);
		}
	}
	
	
	
	Arrays.sort(number, new Comparator<String>() {
		@Override
		public int compare(String a, String b) {
			String A = a+b;
			String B = b+a;
			
			return -A.compareTo(B);
		}
	});
	
	
	
	
	int count = 0;
	String result = "";
	for(int i=0; i<K; i++) {
		result += number[i];
		
		
		if(Integer.parseInt(number[i]) == max && count == 0) {
		
			int M = N-K;
			while(M-->0) {
				result+=number[i];
			}
			
			count = 1;
		}
	}
	System.out.println(result);
	
	}
}

 

 

참고 블로그 : https://ddae9.tistory.com/7

[백준 1422] 숫자의 신