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

문제

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

 

풀이

처음엔 그냥 순열 문제인줄 알고 DFS로 풀려고 했는데 numbers의 길이가 10만이라 순열로 풀면 시간 초과나서 안되겠구나 싶었다,,,

 

그래서 정렬 문제라 해서 정렬로 풀려고 해봤는데 모르겠어서 해답을 찾아봤다 ㅠㅠㅠ

 

문자열(수)을 앞뒤로 이어 붙인 것 중에 큰 순서대로 정렬을 하면 됨!

            // 문자열 o1, o2를 연결해서 더 큰게 앞으로 오게 정렬
            Arrays.sort(strArr, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return (o2 + o1).compareTo(o1 + o2);
                }
            });

배열을 내 입맛재로 기준을 정해섯 정렬하는 법을 잘 알아 놓자!

 

numbers가 [0, 0, 0] 이런 식으로 주어질 수도 있기 때문에 이런 경우도 생각해줘야 함!

 

자세한건 주석으로!

 

 

코드

// 코딩테스트 연습 - 정렬 - 가장 큰 수
// https://programmers.co.kr/learn/courses/30/lessons/42746

package PROGRAMMERS.level2;

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

public class Num42746_가장큰수 {
    private static class Solution {
        private String solution(int[] numbers) {
            String[] strArr = new String[numbers.length];
            for (int i = 0; i < strArr.length; i++) {
                strArr[i] = Integer.toString(numbers[i]);
            }

            // 문자열 o1, o2를 연결해서 더 큰게 앞으로 오게 정렬
            Arrays.sort(strArr, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return (o2 + o1).compareTo(o1 + o2);
                }
            });



            // 얘는 안됨!
            // if (strArr[0] == "0") {
            // 정렬했는데 0이 맨 첨에 있는거면 0이 제일 크다는 거 -> 그니까 걍 0 반환
            // (numbers가 [0,0,0] 등으로 주어지는 경우는 "000"이 아닌 "0" 리턴)
            if (strArr[0].equals("0")) {
                return "0";
            } else {
                return String.join("", strArr);
            }


//            String answer = "";
//            // int -> String 배열로
//            ArrayList<String> strNumbers = new ArrayList();
//            for(Integer num : numbers){
//                strNumbers.add(String.valueOf(num));
//            }
//            // 내림차순 정렬
//            Collections.sort(strNumbers, (a, b) -> (b + a).compareTo(a + b));
//            // numbers가 [0,0,0] 등으로 주어지는 경우는 "000"이 아닌 "0" 리턴
//            if(strNumbers.get(0).startsWith("0")) return "0";
//            // answer에 정렬된 것을 담기
//            for(String s : strNumbers){
//                answer += s;
//            }
//            return answer;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(sol.solution(new int[]{6, 10, 2}));
        System.out.println(sol.solution(new int[]{3, 30, 34, 5, 9}));
    }
}