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

1.  문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

2. 제한사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

3. 입출력예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

4. 풀이(과정 or 최종)

Solution 1 ( 처음에 생각한것, Arrays.sort로 정렬 )

먼저 큰값이 앞으로 오면 되나? 라는 단순한 생각으로는 풀리지 않았다. (당연)

 

10 과 2 가 있으면 10이 크지만 두 숫자를 문자열로 붙이면 각각 102, 210이 되서 2가 앞으로 오는게 더 큰 숫자가 된다.

그래서 숫자 o1 과 o2 를 문자열로 붙여서 비교해야 한다.

사용자가 정의 한대로 정렬을 하기 위하여 sort 메서드 내에 Comparator 인터페이스를 구현하였다.

<Integer> void java.util.Arrays.sort(Integer[] a, Comparator<? super Integer> c)

import java.util.*;
import java.util.stream.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        // Arrays.sort(numbers);
        // sort는 아니다.그렇다고 한글자씩 떼서 볼 수도 없다.
        
        Integer[] refInt = new Integer[numbers.length];
        for(int i =0; i<numbers.length; i++){
          refInt[i] = numbers[i];
        }
        
        // Comparator안에 구현해야 할게 compare하나 이므로 람다식으로 구현 가능
        // Arrays.sort(refInt, (o1, o2) -> {
        Arrays.sort(refInt, new Comparator<Integer>() {
          // Override된 compare 함수를 어떻게 정의하냐에 따라서 다양한 정렬이 가능
          @Override
          public int compare(Integer o1, Integer o2) {
              String v1 = "" + o1 + o2;
              String v2 = "" + o2 + o1;
              int v = Integer.parseInt(v2)-Integer.parseInt(v1);
              return v;
          }
        });

        for(int n : refInt){ answer += n; }
        if(answer.startsWith("0"));
        return answer;
      }
  }

Solution 2 ( 두번째, List와 Collection.sort(List, Comparator) , String.join(), StringBuilder 사용 )

Arrays.sort와 Collection.sort를 비교해보기 위해서 List로 비교요소를 만들어서 용자 정의 정렬을 해보았다.

<String> void java.util.Collections.sort(List<String> list, Comparator<? super String> c)

import java.util.*;
import java.util.stream.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
    
        List<String> listStr = new ArrayList<>();
        for(int num : numbers) listStr.add(String.valueOf(num));
        Collections.sort(listStr, new Comparator<String>() {
          @Override
          public int compare(String o1, String o2) {
            String v1 = o1 + o2;
            String v2 = o2 + o1;
            int v = Integer.parseInt(v2)-Integer.parseInt(v1);
            return v ;
          }
        });
        
	// 1. String.join 으로 문자열 합치기
        // answer = String.join("", listStr);
        
        // 2. StringBuilder로 문자열 합치기
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < listStr.size(); i++){
            stringBuilder.append(listStr.get(i));
        }
        answer = stringBuilder.toString();

        // 0 으로 시작한다는건 뒤에가 다 0이라는거지
        // 0보다 큰수가 있으면 맨 앞으로 왔을테니까!
        if(answer.startsWith("0"));
        return answer;
    }
}

Solution 3 ( 어떤 분의 쩌는 코드11111 )

stream.. 개머싯성..1111

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
       String answer = "";
        answer = Arrays.stream(numbers)
        .mapToObj(String::valueOf)
        .sorted((s1, s2) -> -s1.concat(s2).compareTo(s2.concat(s1)))
        .reduce("", (s1, s2) -> s1.equals("0") && s2.equals("0") ? "0" : s1.concat(s2));
        return answer;
    }
}

Solution 4 ( 어떤 분의 쩌는 코드2222 )

stream.. 짱짱...2222

import java.util.*;
import java.util.stream.*;
class Solution {
    public String solution(int[] numbers) {
       List<String> result = Arrays.stream(numbers)
          .mapToObj(n -> String.valueOf(n))
          .collect(Collectors.toList());
        Collections.sort(result, (s1, s2) -> (s2+s1).compareTo(s1+s2));

        if(result.get(0).equals("0")) {  return "0"; }

        return result.stream().collect(Collectors.joining());
    }
}

5. 결과 

풀이 과정 별 결과

적합성 및 효율성 테스트 결과

 

6. 마치며

프로그래머스에 올라가있는 내 풀이는 엄청 똥코드다.

2번 풀이에서 Integer로 List만들고, answer += number 로 String을 만들었다.

그야말로 효율성 최악 ㅎㅅㅎ.

그래서 아니 애초에 Stirng List를 만들고 합쳐 버리면 되는거 아녀?! 해서 최종 2번코드가 나왔다.

그리고 어쨌든 사용자 정의 정렬을 해보라는 것이 핵심인것같다.

두개를 비교해 보려고 1번 2번 코드로 각각 풀어보았다.

그리고 3,4번 코드는..워후 진짜 스트림 ㅠㅠ 대단존경.. 나는 야만인수준..

아 한문제 푸는데 이것저것 하니까 2시간넘게 본것같다.

빨리자야되는데.. 내일 운전해야되는데.. 끄빠!

( 아 머야 Comparable 은 언제쓰는거야?! )