[백준 16496번] 큰 수 만들기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 입력받은 숫자들의 우선순위를 찾아 정렬하여 풀어보았습니다.

 

먼저 입력받은 숫자 3, 30, 34는 어느 것이 우선순위가 높은 숫자가 되는지 알아야 합니다.

 

3과 30 둘 중 어느 숫자가 더 높은 우선순위를 가질까요?

 

3이 먼저 오면 330 3이 늦게 오면 303이 되어 3이 30보다 우선순위가 높습니다.

 

그럼 3과 34는 어떤 수가 우선순위가 높을까요?

 

이번에는 34가 우선순위가 높습니다. 343이 334보다 큰 수이기 때문입니다.

 

이번에는 3과 같은 우선순위에 있는 수들은 무엇일까요?

 

333, 3333, 33333 ···· 3333333333 이 수들은 모두 3과 같은 우선순위의 수입니다.

 

이번에는 30과 같은 우선순위 수는 30, 3030, 303030, 30303030, 3030303030입니다.

 

이제 1 자릿수 3과 2 자릿수 와의 비교는 3을 2자리 수로 변경하여 두 수의 크기를 비교하면 쉽게 우선순위를 찾을 수 있습니다.

 

즉 3과 같은 우선순위인 33과 비교를 하는 것입니다.

 

입력으로 주워지는 숫자의 최대 자릿수는 10자리 이므로 입력받은 수를 반복하여 10자리로 만든 수를 크기 비교하여 우선순위를 찾을 수 있습니다.

 

하여 3을 입력으로 받은 경우 3333333333으로 숫자를 변경하고 30을 입력으로 받은 경우 3030303030의 숫자로 변경하여 두 수를 비교하는 것입니다.

 

6. 코드

전체 코드는 Git에 있습니다.

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder stringBuilder = new StringBuilder();
    StringTokenizer stringTokenizer;

    int num = Integer.parseInt(br.readLine());
    stringTokenizer = new StringTokenizer(br.readLine());

    List<Number> numberList = new ArrayList<>();

    for(int i=0; i<num; i++)
        numberList.add(new Number(stringTokenizer.nextToken()));

    Collections.sort(numberList);

    for(int i=num-1; i>-1; i--)
        stringBuilder.append(numberList.get(i).originalNumber);

    System.out.println(new BigInteger(stringBuilder.toString()).toString());
}

public static class Number implements Comparable<Number>{
	long originalNumber;
	StringBuilder numberString = new StringBuilder();

	public Number(String num){
		this.originalNumber = Long.parseLong(num);

		for(int i=0; i<10; i++)
			numberString.append(num.charAt(i%num.length()));
	}

	@Override
	public int compareTo(Number o) {
		if(Long.parseLong(this.numberString.toString()) - Long.parseLong(o.numberString.toString()) == 0)
			return 0;
		else if(Long.parseLong(this.numberString.toString()) - Long.parseLong(o.numberString.toString()) > 0)
			return 1;
		else return -1;
	}
}