[Java] 가장 큰 수 - Lv2 프로그래머스 정렬 / 프로그래머스 고득점 Kit

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

프로그래머스

 

 

풀이

---

첫 풀이

numbers.length <= 100,000이지만 복습할 겸 DFS로 풀어봤다.

통과돼도 수정해서 풀 예정이었지만 역시나 안됨  시간초과 메모리초과 ㅋㅋㅋ

 

class Solution{

    int max = 0;

    public String solution(int[] numbers) {
        boolean[] bl = new boolean[numbers.length];
        String[] strs = new String[numbers.length];
        for(int i=0; i<strs.length; i++){
            strs[i]=String.valueOf(numbers[i]);
        }
        
        dfs(strs, bl, 0, "");
        return String.valueOf(max);
    }

    public void dfs(String[] strs, boolean[] bl, int idx, String word){
        if(idx == strs.length){
            max = Math.max(Integer.parseInt(word), max);
            return;

        }
        for(int i=0; i<strs.length; i++){
            if(bl[i]) continue;
            bl[i]=true;
            dfs(strs, bl, idx+1, word+strs[i]);
            bl[i]=false;
        }
        
    }
}

 

다른 방법을 찾아야했다.

 

 

두번째 풀이

Comparator 인터페이스를 오버라이딩하여 사용하거나

lambda식을 활용하여 정렬을 진행할 수 있다.

import java.util.Arrays;

class Solution{
	 
    public String solution(int[] numbers) {

    	String[] strArr = new String[numbers.length];
    	
    	for(int i=0; i<numbers.length; i++) {
    		strArr[i] = String.valueOf(numbers[i]);
    	}
    	
    	Arrays.sort(strArr, (o1, o2) -> (o2+o1).compareTo(o1+o2));
    	
    	StringBuilder sb = new StringBuilder();
    	
    	for(String s : strArr)sb.append(s);
    	
    	if(sb.charAt(0)=='0') return "0";
    	
    	else return sb.toString();
    	
    }
}

sort를 통해, 두 문자열을 이어붙인 값을 비교하고, 내림차순으로 정렬한다.