프로그래머스 <가장 큰 수>

문제

1. 정수가 여러개 주어진다
2. 그 정수들을 이어붙여 가장 큰 수를 만들어 보자

접근 방법

1. 우선 숫자를 String 형태로 바꿔준다.
2. 위에서 바꾼 String값들을 내림차순 상태로 sorting한다.
3. 수를 이어붙인다.
4. 가장 큰 수가 0일 경우에는 0을 리턴하도록 한다.

풀이

public class BigNumber {
    public String solution(int[] numbers) {
        String answer = "";
        String str_numbers[] = new String[numbers.length];

        for (int i = 0; i < str_numbers.length; i++) {
            str_numbers[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(str_numbers, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
                // 오름차순 (o1 + o2).compareTo(o1 + o2)
            }
        });

        if (str_numbers[0].startsWith("0")) {
            answer += "0";
        } else {
            for (int i = 0; i < str_numbers.length; i++) {
                answer += str_numbers[i];
            }
        }

        return answer;
    }
}

추가

Comparator

Arrays.sort(str_numbers, new Comparator<String>() {
	@Override
    public int compare(String o1, String o2) {
    	return (o2 + o1).compareTo(o1 + o2);
    	// 오름차순 (o1 + o2).compareTo(o2 + o1)
    }
});

이 때 Comparator에 대해 알아보자.

Comparator는 interface로 compare 메서드를 오버라이딩 시킨다. 이 compare 메서드는 두개의 수를 비교하게 된다. 이 때는 return값에 compareTo 메서드가 쓰인다.

("3430").compareTo("3034") -> 4 (양수)
("3034").compareTo("3430") -> -4 (음수)
("3430").compareTo("3430") -> 0 

compareTo 메서드는 양수, 음수 그리고 0을 반환한다. String값을 비교하는 메서드인데 compare 메서드 안에서 String값을 정렬하고 싶다면 CompareTo를, 단순 수의 대소를 비교하고 싶다면 연산만 하면 될 것이다.

본론으로 돌아가 Comparator interface 안에 있는 compare 메서드는 두개의 문자를 비교하게 되는데, 이 때 return값이 양수가 나온다면 o2와 o1의 위치를 바꾸고 음수가 나온다면 그대로 두게 된다.

o1이 30이고 o2가 34라고 해보자. (o2+o1).compareTo(o1+o2)는 ("3430").compareTo("3034") 즉 return값은 4로 양수가 나오게 된다.
양수값이 return 되었으므로 o1과 o2의 위치는 바뀌게 되고, 우리의 바램대로 큰 수가 더 위로 가게 된다.

StringBuilder()

다른 사람들의 풀이를 보다가 댓글에 써져있는 것을 보았다.
"문자열을 합칠 때 StringBuilder()를 쓰면 성능이 훨씬 좋아집니다"

그래서 StringBuilder()를 통한 기능들을 알아보기로 했다.

StringBuilder sb = new StringBuilder("Default String");
System.out.println(sb.length()); // 14

System.out.println(sb.append("!")); // Default String!

System.out println (sb.reverse()); // !gnirts tluafeD

StringBuilder sb = new StringBuilder("123456");
System.out.println(sb.replace(0, 1, "A")); // A23456

StringBuilder sb = new StringBuilder("123456");
sb.setCharAt(0, '*');
System.out.println(sb.toString()); // *23456

StringBuilder sb = new StringBuilder("123456");
System.out.println(sb.substring(0,2)); // 12

일반 String의 기능들과 크게 다를 바 없다.

-> String 사용

-> StringBuilder 사용

프로그래머스의 테스트코드를 빌려왔다. 똑같게 통과가 되었지만 실행 시간이나 용량부분에서 압도적으로 차이가 난다.
String은 매 연산마다 String 객체가 만들어진다고 한다. 하지만 StringBuilder는 한번 만들어지고 그것 안에 계속 들어가기 때문에 훨씬 더 효율적인 코드를 만들어낼 수 있다.