[프로그래머스 | Java Lv.2] 가장 큰 수

문제 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

---

삽질

 

[6, 10, 2] 일 때 배열은 [10, 2, 6]으로 정렬

[3, 30, 34, 5, 9]일 때는 [30, 3, 34, 5, 9]로 정렬

 

첫번째 자리의 숫자로 먼저 정렬하고,

그게 같다면 그 뒷 자리부터는

1. 뒷자리가 첫번째 자리보다 클 때 

2. 뒷자리가 첫번째 자리와 같거나 없을 때

3. 뒷자리가 첫번째 자리보다 작을 때

순서로 정렬

 

..

 

처음엔 우선 순위 큐를 사용해서 Comparable을 활용해 위 알고리즘을 적용시켜 보려고 했는데 실패 

PriorityQueue<Integer> pq = new PriorityQueue<Integer>((o1, o2)-> {
     if(o1.toString().charAt(0) == o2.toString().charAt(0)){
           for(int i=0; i<o1/10; i++){
                if(o1.toString().charAt(i) != o2.toString().charAt(i))
                    return o1.toString().charAt(i) - o2.toString().charAt(i);
                }
            }
            
      else return o1.toString().charAt(0) - o2.toString().charAt(0);
	}

 

 

---

접근 방법이 틀렸었다

 

문자열로 받고, {30, 33, 35, 3} 을 정렬할 때 {35, 33, 3, 30}이 되어야 한다. 

이때 이걸 수학적으로 접근하기 보다는 문자열 연산을 통해 3033, 3330을 비교해서 앞에 오는 게 큰 것

3, 30 -> 330, 303 : 3이 더 큼

 

Comparator의 compareTo() 메서드

이제 이거를 Comparator의 compareTo() 메서드를 활용해야 했던 문제

 

compareTo( )의 반환 값은 Int 이지만 두 객체가 같으면 0, 비교하는 값보다 크면 양수 작으면 음수를 반환하도록 구현을 해야하고,

compare( ) 도 객체를 비교해서 음수, 0, 양수 중 하나를 반환하도록 구현해야 함

(오른쪽이 크면 음수, 작으면 양수)

        Arrays.sort(s, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });

 

이때 (o2+o1).compareTo(o1+o2) 순서 조심!

반대로 하면 반대 결과가 나온다. 

 

3, 30이 각각 o1, o2라고 할 때,

o1+02 = 330

o2+o1 = 303

 

(o2 + o1).compareTo(o1 + o2)를 사용하면, 만약 o2+o1이 o1+o2보다 사전 순으로 더 크다면 양수를 반환

이는 o2가 o1보다 앞에 와야 함을 의미 -> 정렬 기준으로서 o2를 더 앞쪽에 위치시킴

 

StringBuilder

String을 합치는 연산이 많을수록 StringBuilder가 유리

StringBuilder 이용해 append()

 

가장 큰 값이 0 일 때를 추가적으로 고려

이것을 안지켜주면 테스트케이스 한 개 때문에 실패됨

if(s[0].equals("0")) return "0";

---

최종 코드 

 

package week2.baek.sort;

import java.util.*;

public class Ex2 {
    public String solution(int[] numbers) {
        String[] s = new String[numbers.length];
        for(int i=0; i< numbers.length; i++) {
            s[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(s, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });

        if(s[0].equals("0")) return "0";

        StringBuilder sb = new StringBuilder();

        for (String str : s) {
            sb.append(str);
        }

        return sb.toString();
    }
}

class Ex2Main {
    public static void main(String[] args) {
        Ex2 ex2 = new Ex2();
        int[] numbers = {6, 10, 2};
        int[] numbers2 = {3, 30, 34, 5, 9};
        System.out.println(ex2.solution(numbers));
        System.out.println(ex2.solution(numbers2));
    }
}

---

참고

https://dding9code.tistory.com/68

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