가장 큰 수

yonii·2021년 1월 13일

sorting 알고리즘 프로그래머스

프로그래머스 - 코딩테스트 고득점 Kit

목록 보기

4/10

가장 큰 수

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

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

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

제한 사항

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

입력

1: [6, 10, 2]
2: [3, 30, 34, 5, 9]

출력

1: "6210"
2: "9534330"

틀린 구현 코드

import java.util.Arrays;

public class Solution {

    static String[] stringArray;
    public String solution(int[] numbers) {
        String answer = "";
        stringArray = new String[numbers.length];

        //문자열 배열로 전환
        for(int i=0;i<numbers.length;i++){
            stringArray[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(numbers); // 배열 정렬
        int maxLength = String.valueOf(numbers[numbers.length-1]).length();
        String[] transformArray = stringArray.clone();

        for(int i=0;i<transformArray.length;i++){
            //같아질때까지 길이 맞춤
            char tmp = transformArray[i].charAt(transformArray[i].length()-1);
            while(maxLength>transformArray[i].length()){
                transformArray[i]+=tmp;
            }
        }

        sort(transformArray,0,transformArray.length-1);
    

        //알고리즘 짠 부분 
        for(int i=0;i<stringArray.length;i++){

            if(i==stringArray.length-1){
                answer+=stringArray[i];
                break;
            }
            String before = stringArray[i] + stringArray[i+1];
            String after = stringArray[i+1] + stringArray[i];

            if(Integer.parseInt(before)>Integer.parseInt(after)){
                answer+=stringArray[i] + stringArray[i+1];
            }
            else{
                answer+= stringArray[i+1] + stringArray[i];
            }

            i=i+1;

            if(Integer.parseInt(String.valueOf(answer.charAt(0)))==0){
                answer="0";
            }
        }

        return answer;
    }


    //내림차순 퀵정렬
    public void sort(String[] data, int l, int r){
        int left = l;
        int right = r;
        String pivot = data[(l+r)/2];

        do{
            while(Integer.parseInt(data[left]) > Integer.parseInt(pivot)) left++;
            while(Integer.parseInt(data[right]) < Integer.parseInt(pivot)) right--;
            if(left <= right){
                String temp = data[left];
                data[left] = data[right];
                data[right] = temp;

                temp = stringArray[left];
                stringArray[left] = stringArray[right];
                stringArray[right] = temp;

                left++;
                right--;
            }
        }while (left <= right);

        if(l < right) sort(data, l, right);
        if(r > left) sort(data, left, r);
    }


    public static void swap(int i1, int i2) {
        String temp = stringArray[i1];
        stringArray[i1] = stringArray[i2];
        stringArray[i2] = temp;
    }

}

구현 코드

import java.util.Arrays;

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

        //문자열 배열로 전환
        for(int i=0;i<numbers.length;i++){
            stringArray[i] = String.valueOf(numbers[i]);
        }

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

				//test
        for(int i=0;i<stringArray.length;i++){
            System.out.print(stringArray[i]+" ");
        }

        return stringArray[0].equals("0")? stringArray[0]: String.join("",stringArray);
    }
   }

알고리즘 자체를 오래 고민한 문제. 어렵게 생각해서 삽질도 많이 했다.

처음에는 보자마자 순열로 풀면 되겠네 하고 풀었음. 이때부터 삽질의 시작.

순열 찾아서 Max를 뽑게 했더니 시간초과가 났음 ->
시간초과..? 퀵소트를 써볼까? (라이브러리에서 제공하는 Collection.sort의 시간복잡도가 O (n * log (n)) 인줄 몰랐음) 하고 부랴부랴 퀵소트 구현해서 함 ->
코드 더 복잡 역시 안됨. 조합문제임을 인식..(시간복잡도가 O(n!)으로 미친놈..)
-> 알고리즘 짜자..해서 지우고 새로 시작함.