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

기본적인 정렬 문제였음.

시간복잡도 생각해보기

최대 N이 10의 5승이므로 O(logN)으로 해결 필요

• 숫자 N개를 String으로 변환하기 -> O(N)
• 숫자 두개를 더했을때 큰 것 정렬하기 -> O(logN)
• 숫자 출력하기 -> O(N)
• 총 O(logN)

풀이 아이디어

• 숫자를 모두 String값으로 만들고 두개를 더해서 큰 값이 되는 것을 정렬해주면 되는 문제였다

의사코드 / 풀이 과정

for(int num: numbers){
    list.add(String.valueOf(num));             
}
Collections.sort(list,(a,b)->{
    return (b+a).compareTo(a+b);
});
StringBuilder result = new StringBuilder();
for(String str: list) {
    result.append(str);
}

Collections.sort(list,(a,b)->{
    return (b+a).compareTo(a+b);
});

가 가장 중요한 부분이 아니였을까 싶다.
String 값으로 변환했을 때 숫자 비교가 가능한지를 몰랐던 점이 크다.

문자열 비교지만, 숫자로 생각할 수 있는 큰 값이 먼저 오도록 하여 결국 숫자처럼 동작한다.
예를 들어, "934"가 "349"보다 사전 순으로 더 크기 때문에, "9"가 "34"보다 먼저 오도록 정렬된다.

(b + a).compareTo(a + b)를 사용한 이유는, 두 문자열을 결합하여 그 결합된 값을 비교하고, a+b가 더크면 음수가 나오기 때문에 b+a가 먼저 나오도록 정렬된다.

틀린코드

class Solution {
public String solution(int[] numbers) {
List<char[]> list = new ArrayList<>();
    for(int num: numbers){
        char[] numCharArrays = (String.valueOf(num)).toCharArray();
        list.add(numCharArrays);             
    }
    Collections.sort(list,(a,b)->{

     int min = Math.min(a.length, b.length);
     for(int i=0;i < min; i++) {
      int aV = Character.getNumericValue(a[i]);
      int bV = Character.getNumericValue(b[i]);
      if(aV != bV) {
       return Integer.compare(bV, aV);
      }
     }
     return Integer.compare(b[0],a[0]);
    });
    StringBuilder result = new StringBuilder();
    for(char[] c: list) {
     result.append(new String(c));
    }
    return result.toString();
  }
}

• 숫자를 char 배열로 만들어서 하나씩 비교해 정렬하려고 했다

  [3, 30, 34, 5, 9]
  기댓값 〉    "9534330"
  실행 결과 〉    실행한 결괏값 "9534303"이 기댓값 "9534330"과 다릅니다

• 이런 결과가 떠서 이유를 너무 잘 알겠는데 예외처리할게 너무 복잡해서 포기하고 답봤다