[정렬] 가장 큰 수

1차 시도

public class Solution {
    public static void swap(int[] numbers, int leftIndex, int rightIndex) {
        int temp = numbers[leftIndex];
        numbers[leftIndex] = numbers[rightIndex];
        numbers[rightIndex] = temp;
    }

    public static void sort(int[] numbers, int maxNum) {
        if (maxNum <= 0) return;

        for (int index = 0; index < numbers.length - 1; index++) {
            int left = numbers[index];
            int right = numbers[index + 1];

            if (isRequireSwap(left, right)) {
                swap(numbers, index, index + 1);
            }
        }

        sort(numbers, maxNum - 1);
    }

    public static int getValue(String value, int i) {
        int idx = i;

        if (value.length() < i + 1) {
            idx = value.length() - 1;
        }

        return Integer.parseInt(String.valueOf(value.charAt(idx)));
    }

    public static boolean isRequireSwap(int leftValue, int rightValue) {
        String left = String.valueOf(leftValue);
        String right = String.valueOf(rightValue);

        int diff = left.length() - right.length();

        for (int i = 0; i < left.length() + Math.abs(diff); i++) {
            int ll = getValue(left, i);
            int rr = getValue(right, i);
            if (rr > ll) return true;
        }

        return false;
    }

    public static String makeAnswer(int[] numbers) {
        StringBuilder answer = new StringBuilder();

        for (int number : numbers) {
            answer.append(number);
        }

        return answer.toString();
    }

    public static String solution(int[] numbers) {
        sort(numbers, numbers.length);

        return makeAnswer(numbers);
    }

    public static void main(String[] args) {
        String answer = solution(new int[]{3, 30, 34, 5, 9});
        System.out.println(answer);
    }
}

자리수로 비교 하였으나 시간 초과로 실패

2차 시도

public class Solution2 {
    public static void main(String[] args) {
        String answer = solution(new int[]{3, 30, 34, 5, 9});
        System.out.println(answer);
    }

    public static String solution(int[] numbers) {
        String[] strings = numbersToStrings(numbers);

        sort(strings);

        String answer = answer(strings);

        return answer.startsWith("0") ? "0" : answer;
    }

    private static String answer(String[] result) {
        return String.join("", result);
    }

    private static void sort(String[] strings) {
        Arrays.sort(strings, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
    }

    private static String[] numbersToStrings(int[] numbers) {
        String[] result = new String[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            result[i] = numbers[i] + "";
        }

        return result;
    }
}

문자열로 변환한 후 통과. 0 이 중복 되는 경우를 생각하지 못해 삽질

통과 후에 1차 코드 변경 해봄

public class Solution {
    public static void swap(String[] strings, int leftIndex, int rightIndex) {
        String temp = strings[leftIndex];
        strings[leftIndex] = strings[rightIndex];
        strings[rightIndex] = temp;
    }

    public static void sort(String[] strings, int count) {
        if (count > strings.length) return;

        for (int index = 0; index < strings.length - 1; index++) {
            String left = strings[index];
            String right = strings[index + 1];

            if (isRequireSwap(left, right)) {
                swap(strings, index, index + 1);
            }
        }

        sort(strings, ++count);
    }

    public static boolean isRequireSwap(String left, String right) {
        return (left + right).compareTo(right + left) < 0;
    }

    private static String[] numbersToStrings(int[] numbers) {
        String[] result = new String[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            result[i] = numbers[i] + "";
        }

        return result;
    }

    public static String makeAnswer(String[] strings) {
        return String.join("", strings);
    }

    public static String solution(int[] numbers) {
        String[] strings = numbersToStrings(numbers);

        sort(strings, 0);

        String answer = makeAnswer(strings);

        return answer.startsWith("0") ? "0" : answer;
    }

    public static void main(String[] args) {
        String answer = solution(new int[]{3, 30, 34, 5, 9});
        System.out.println(answer);
    }
}

하지만 시간초과. 정렬 알고리즘이 문제인거 같음. 알아보고 다시 정리할 것!

좋은 웹페이지 즐겨찾기