프로그래머스 lv2 가장 큰 수

문제 링크

가장 큰 수

풀이

import java.util.Arrays;
import java.util.Comparator;

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

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

        list.sort((a, b) -> {
            String as = String.valueOf(a);
            String bs = String.valueOf(b);
            return Integer.compare(Integer.parseInt(bs + as), Integer.parseInt(as + bs));
        });

        StringBuilder sb = new StringBuilder();
        for(Integer i : list) {
            sb.append(i);
        }
        answer = sb.toString();
        if(answer.charAt(0) == '0') {
            return "0";
        }else {
            return answer;
        }
    }
}

소감

• 알고리즘 문제를 풀 때마다 느끼는거지만 항상 어떻게 풀어야하는지를 모른다.
• 문제의 방향성을 알아야하는데, 문제의 방향성을 잡지 못 한다. 이게 늘 문제다.
• 이번 문제도 처음에는 당연하게 순열로 풀어야하는줄 알았다.
• 그러나, 순열로 풀이했더니 계속 런타임 에러가 떴고, 멘붕이 왔다.
• 제한 사항을 보니 다음과 같이 있었다.
  • numbers의 길이는 1 이상 100,000 이하입니다.
  • numbers의 원소는 0 이상 1,000 이하입니다.
  • 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
• 그니까..1000이 100,000개가 있을 수도 있다는 소리였다.
• 그래서 처음에는 그럼 BigInteger를 사용하면 되지 않을까? 했다. 결론은 시간초과. 숫자가 너무 많았다.
• 결론은 못풀었다. 그래서 답을 봤다. 개같다.
• 위의 코드에 대해서는 다음과 같이 풀이한다.
  • 모든 숫자에 대해서 list에 넣어주고, list의 sort메서드를 사용한다. list.sort는 음수를 오름차순으로 정렬한다.
  • Integer.compare()를 수행한다. Integer 라이브러리의 compare 함수를 살펴보면 x==y 인 경우 0을 반환, x < y인 경우 음수, x > y인 경우 양수를 반환한다.
  • 그렇기에, b + a가 먼저 나오게 했다. 왜냐하면 b + a가 a + b보다 큰 경우에는 b가 앞에 위치해야하기 때문이다.