Programmers - 정렬 [가장 큰 수]

1. 문제

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers                                                                 return

[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

2. 내풀이

import java.util.*;

class Number implements Comparable<Number> {
    private int number;
    private int resizedNumber;

    public int getNumber() {
        return number;
    }

    public Number(int number, int biggestNumber) {
        this.number = number;
        int sizeOfNumber = Integer.toString(number).length();
        // 가장 큰수의 자리만큼 0으로 채운다.
        resizedNumber = (int) (number * Math.pow(10, Integer.toString(biggestNumber).length() - sizeOfNumber));
    }

    // 오름차순은 작으면 양수 반환 같으면 0 크면 음수 같으면 원래수를 비교해서 작으면 앞에 오게한다.
    @Override
    public int compareTo(Number num) {
        if (this.resizedNumber < num.resizedNumber) {
            return 1;
        } else if (this.resizedNumber == num.resizedNumber) {
            if (this.number < num.number) return 1;
            return 0;
        }
        return -1;
    }
}

class BiggestNumber {
    public String solution(int[] numbers) {
        // 입력number를 ArrayList로 변경한다.
        ArrayList<Number> numbers1 = new ArrayList<>();
        // 가장 큰수를 찾자.
        int biggestNumber = 0;
        for (int num : numbers) {
            if (biggestNumber < num) biggestNumber = num;
        }

        // numbers를 객체에 담는다.
        for (int num : numbers) {
            numbers1.add(new Number(num, biggestNumber));
        }
        // 정렬
        Collections.sort(numbers1);

        String answer = "";
        if(numbers1.get(0).getNumber() == 0){
            return "0";
        }
        for (Number num : numbers1) {
            answer += Integer.toString(num.getNumber());
        }
        return answer;
    }

    public static void main(String[] args) {
        BiggestNumber biggestNumber = new BiggestNumber();
        int[] numbers = {0, 0, 0, 0, 0};
        System.out.println(biggestNumber.solution(numbers));
    }
}

- 객체로 만들어 접근했는데 틀렸다. 접근 방식은 다음과 가다. 원소를 가장 큰 자리수까지 맞춘다. 끝자리 0을 채워서

그다음 객체를 새롭게 만든 수로 정렬시킨다. 이때 같은 수는 원래수를 비교해서 같으면 0 더 크면 1로 오름차순으로 정렬시킨다. 이후 순서대로 원래숫자를 이어 붙인다.

 

특별한 예외처리로서 numbers = {0, 0 , 0, 0} 인경우 0000을 반환하므로 0으로 반환 하게끔 처리를 해줘야한다.

테스트 1 〉	실패 (1753.78ms, 356MB)
테스트 2 〉	실패 (669.89ms, 354MB)
테스트 3 〉	실패 (2821.73ms, 359MB)
테스트 4 〉	실패 (14.00ms, 58.1MB)
테스트 5 〉	실패 (1392.34ms, 356MB)
테스트 6 〉	실패 (1169.56ms, 355MB)
테스트 7 〉	통과 (2.22ms, 52.5MB)
테스트 8 〉	통과 (5.41ms, 52.9MB)
테스트 9 〉	통과 (4.00ms, 52.2MB)
테스트 10 〉	실패 (2.25ms, 52.8MB)
테스트 11 〉	통과 (0.59ms, 54.1MB)

이런 결과가 나오는데, 실패요인들을 보면 대부분 시간복잡도와 공간 복잡도가 큰것으로 보인다.

대체 무슨 예외가 있을런가.

 

다른 사람풀이를 참고삼아 숫자를 비교하는 부분을 수정해서 통과했다.

import java.util.*;

class Number {
    private int number;

    public int getNumber() {
        return number;
    }

    public Number(int number, int biggestNumber) {
        this.number = number;
    }

}

// 두개 숫자를 합쳐보고 더 크면 오름 차순으로 정렬
class AscendingString implements Comparator<Number> {
    @Override
    public int compare(Number a, Number b) {
        String thisNumber = Integer.toString(a.getNumber());
        String numNumber = Integer.toString(b.getNumber());
        return (numNumber + thisNumber).compareTo(thisNumber + numNumber);
    }
}


class BiggestNumber {
    public String solution(int[] numbers) {
        // 입력number를 ArrayList로 변경한다.
        ArrayList<Number> numbers1 = new ArrayList<>();
        // 가장 큰수를 찾자.
        int biggestNumber = 0;
        for (int num : numbers) {
            if (biggestNumber < num) biggestNumber = num;
        }

        // numbers를 객체에 담는다.
        for (int num : numbers) {
            numbers1.add(new Number(num, biggestNumber));
        }
        // 정렬
        Collections.sort(numbers1, new AscendingString());

        String answer = "";
        if (numbers1.get(0).getNumber() == 0) {
            return "0";
        }
        for (Number num : numbers1) {
            answer += Integer.toString(num.getNumber());
        }
        return answer;
    }

    public static void main(String[] args) {
        BiggestNumber biggestNumber = new BiggestNumber();
        int[] numbers = {1, 1, 2, 1, 101};
        System.out.println(biggestNumber.solution(numbers));
    }


}

- 핵심 내용은 두 숫자를 합쳤을 때, 30 과 3을 비교할때, 303 이 330 보다 작으므로 330으로 정렬해야한다는 것이다.

한줄 코드로 작성이된다.

 

3. 다른 사람 풀이

package pojoPrj;

import java.util.Arrays;
import java.util.Comparator;

class Solution {

	public String solution(int[] numbers) {

		// 숫자를 문자열로 변환
		String[] result = new String[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			result[i] = String.valueOf(numbers[i]);
		}

		// 정렬
		Arrays.sort(result, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

		// 0만 여러개 있는 배열의 경우 하나의 0만 리턴
		if (result[0].equals("0")) {
			return "0";
		}

		String answer = "";
		// 정렬된 문자 하나로 합치기
		for (String a : result) {
			answer += a;
		}
		return answer;
	}
}

- 고인물 플레이다.

여기서 핵심 아이디어를 배워서 내풀이를 수정해보았다.

 

* 람다식 한줄 문법

 (매개변수) -> 명령문;  (리턴값이 있다면 자동으로 수행 결과가 리턴됨)

Arrays.sort(result, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

 

4. Tip

- 문자열 비교를 생각해야한다.

- 문자열 비교시 두문자를 합친후 더 큰 것을 기준으로 오름차순으로 정렬하는 것을 생각해야한다.