프로그래머스 - 정렬 - 가장 큰 수

# 문제 설명

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"

 

# 풀이

1. 경우의 수를 다 만든 다음 가장 높은 수를 리턴?

=> 그러면 반복문을 돌리기가.. 모든 경우의 수 돌리기 => 너무 오래걸릴 듯

 

2. String 타입으로 변환해 크기 정렬해 붙혀 리턴

=> 6, 61, 68 등의 경우 가장 큰 값이 나오지 않음

그래도 일단 식 써보기

  * int -> String 방법

    1. Integer.toString(int)

    2. Integer.valueOf(int)

    3. int + ""

 

public String solution(int[] numbers) {
    String answer = "";
    
    int num = numbers.length;
    String[] temp = new String[num];
    for(int i = 0; i < num; i++) {
        temp[i] = Integer.toString(numbers[i]);
    }
    Arrays.sort(temp, Collections.reverseOrder());

    if(temp[0] == "0") {
        return "0";
    }

    StringBuilder sb = new StringBuilder();
    for(String e : temp) {
        sb.append(e);
    }
    answer = sb.toString();

    return answer;
}

=> 틀림

 

 

3. 인터넷 서칭

3-1. Arrays.sort() 내부에서 Comparator의 compareTo()를 이용하는 방식

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

 

compareTo() 란?

(String 클래스의 compareTo() ) : 두 개의 값을 비교하여 int값으로 반환하는 메서드

Comparable 인터페이스의 compareTo(T o)

- Comparable 인터페이스는 이를 구현하는 각 클래스의 객체를 비교해 객체의 전체 순서를 적용함

- 자기 자신과 매개변수를 비교한다

   a.compareTo(b);

- null값 처리, 오버플로우 방지로 <,>,== 으로 대소비교를 해주는 것이 안전하다

 

(cf. Comparator compare(T o1, T o2))

- 두 매개변수 객체를 비교(자기 자신과 비교 X)

  => 비교를 위해서 Comparator를 구현하는 객체 안 compare() 메서드를 사용해야함

       어떤 객체든지 상관 없지만 일관성이 떨어진다

  => 기능만 사용하고자 익명 객체(클래스)를 사용

 

compareTo()를 정렬에 사용하기

compareTo() 사용 : 사용자가 정의한 기준으로 값 비교하여 int값 리턴

정렬에 사용

=> Arrays.sort(), Collections.sort() 모두 오름차순으로 정렬

    (오름차순 : compareTo()를 사용했을 때 음수인 경우- 양수면 원소 위치 바꿈)

 

# 따라서,

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

o1과 o2를 정렬할 때,

o2+o1이 o1+o2보다 크면 둘의 위치 변경 => 두 값을 붙혔을 때 큰 수가 앞으로 오게 정렬됨

 

public String solution(int[] numbers) {
    String answer = "";
    
    int num = numbers.length;
    String[] temp = new String[num];
    for(int i = 0; i < num; i++) {
        temp[i] = Integer.toString(numbers[i]);
    }
    
    // 정렬 방식 - 두 값을 붙혔을 때 더 크게 나오는 순으로 정렬
    Arrays.sort(temp, ((o1, o2) -> (o2 + o1).compareTo(o1 + o2)));
	
    // String 값이기 때문에 == 으로 판별이 제대로 되지 않음!
    if(temp[0].equals("0")) {
        return "0";
    }

    StringBuilder sb = new StringBuilder();
    for(String e : temp) {
        sb.append(e);
    }
    answer = sb.toString();

    return answer;
}

 

 

 

참고

3-1.

- https://bellog.tistory.com/170

compareTo().

- https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html#method.summary

- https://st-lab.tistory.com/243