가장 큰 수

문제

문제 설명

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. 나열했을 때 가장 크도록 정렬.

처음에는 단순히

Arrays.sort(array, Comparator.reverseOrder()); //array는 String[]

로 정렬했는데 30이 3보다 앞으로 와서 실패.

Math.pow로 자리수 더하기 등등 이런저런 뻘짓을 하다가 깨달았다. 문제 조건 그대로 순서를 바꿔보면 되는 거구나..
3과 30이면 330과 303 비교하는 식.

import java.util.*;

class Solution {
	public String solution(int[] numbers) {

		List<String> strings = new ArrayList<>();
		Boolean isAllZero = true; // 11번 케이스 [0,0,0,0] 통과
		
        for (int number : numbers) {
			if (number != 0) {
				isAllZero = false;
			}
			strings.add(Integer.toString(number));
		}
        
		if(isAllZero) {
			return "0";
		}
        
		strings.sort((o1, o2) -> {
			String s1 = o1 + o2;
			String s2 = o2 + o1;
			return Integer.parseInt(s2) - Integer.parseInt(s1);
		});

		String answer = "";

		for (String string : strings) {
			answer += string;
		}

		return answer;
	}
}

다른 사람 풀이

프로그래머스에서 참고용으로 가져왔다.
주석은 내가 이해하려고 공부하면서 단 것.

class Solution {
    public String solution(int[] numbers) {
        String answer = "";

        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < numbers.length; i++) {
            list.add(numbers[i]);
        }
        Collections.sort(list, (a, b) -> {
            String as = String.valueOf(a), bs = String.valueOf(b);
            return -Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
        });
        StringBuilder sb = new StringBuilder();
        for(Integer i : list) {
            sb.append(i);
        }
        answer = sb.toString();
        
        if(answer.charAt(0) == '0') {
            return "0";
        }else {
            return answer;
        }
    }
}

class Solution {
    public String solution(int[] numbers) {
        String[] nums = new String[numbers.length];

        for (int i=0; i<nums.length; i++) 
            nums[i] = numbers[i] + "";

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

        String ans = "";
        for (int i=0; i<numbers.length; i++)
            ans += nums[i];

        return ans.charAt(0) == '0' ? "0" : ans;
    }
}

StringBuilder가 +=보다 빠르다고 한다.
compare 부분도 참고해서 간결하게 고칠 수 있을 것 같다.

코드 개선

class Solution {
	public String solution(int[] numbers) {

		List<String> strings = new ArrayList<>();
        
		for (int number : numbers) {
			strings.add(Integer.toString(number));
		}

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

		StringBuilder answer = new StringBuilder();
        
        for (String string : strings) {
			answer.append(string);
		}
        
        return answer.charAt(0) == '0'? "0" : answer.toString();
	}
}

람다 축약. StringBuilder 사용.
값이 0인지 체크하는 부분도 다른분들 코드 참고해서 isAllZero에서 answer.charAt(0) == '0'으로 변경.

전부 0인 경우에는 isAllZero 체크로 sort하지 않고 빨리 리턴하고 싶었는데 answer.charAt(0) == '0' 체크가 훨씬 빠르다.
값이 전부 0일 때 성능 향상 vs 그렇지 않을 때 성능 향상 (전부 0일 때도 같은 성능) 중에서 택하자면 후자를 선택하는 게 맞는 것 같다. 값이 전부 0인 케이스보다 그렇지 않은 케이스가 훨씬 많을테니까.

answer.charAt(0) == '0' 에서 따옴표 주의할 것. '0'을 "0"로 쓰는 실수가 있었다.