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

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

프로그래머스

 

풀이 접근 방법

1. 일의 자리가 가장 큰 값이 앞으로 와야하므로, 그 값을 기준으로 정렬한다.

2. 일의 자리 숫자가 같을 때, compareTo()를 사용하여 나머지 숫자를 비교하고 정렬한다.

3. 일의 자리를 기준으로 오름차순 되어있으므로, 뒤에서 부터 String 결과값에 더해준다.

 

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        boolean flag = true;
        for(int num : numbers) {
            if (num != 0) {
                flag = false;
                break;
            } 
        }
        
        if (flag) return "0";
        
        String [] str = new String[numbers.length];
        for(int i = 0; i < str.length; i++) str[i] = String.valueOf(numbers[i]);
        Arrays.sort(str, (n1, n2) -> {
            if (n1.charAt(0) != n2.charAt(0)) {
                return n1.charAt(0) - n2.charAt(0);
            }
            String s1 = n1 + n2;
            String s2 = n2 + n1;
            return s1.compareTo(s2);
        });
        
        
        for(int i = str.length - 1; i >= 0; i--) {
            answer += str[i];
        }
        
        return answer;
    }
}

 

문제풀이 회고

 

길이가 100,000 이므로 O(N^2)인 로직을 짜면 최악의 경우 100억이 되므로 시간 복잡도를 개선해야한다. O(NlogN)은 길이가 5백만 까지 수용 가능하니 정렬을 사용 가능하다.

 

문자열 내 마음대로 정렬하기 문제를 풀고 나니 쉬웠다. 그런데, 로직을 비슷하게 짜니 

[3, 30, 34, 5, 9]

위 예제가 주어졌을 때 "9534330"이 결과값으로 나와야 했는데 내 로직은 "9534303"이 나왔다.

 

"3", "30"에서 나올 수 있는 결과쌍인 "330"과 "303"에 대해서 비교가 필요했다.

String s1 = n1 + n2;
String s2 = n2 + n1;
return s1.compareTo(s2);

그래서 두 값을 비교하게 해서 "330"이 올 수 있도록 구현하였다.

 

Edge Case

모든 테케를 통과했다. 11번 빼고....

 

힌트를 찾아보니 [0, 0, 0] 처럼 모든 정수가 0인 경우의 수가 있었다. 그래서 코드 처음에 모든 정수가 0이면 바로 0을 return하고, 정수가 하나라도 0이 아니라면 바로 break를 해서 시간복잡도를 줄여보았다.