[프로그래머스] 가장 큰 수 (LV2 - JAVA, Python)

프로그래머쓱

해당 글에서는 가장 큰 수 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

 

🔷 문제 설명

 

🔷 문제 풀이

1️⃣ Python 풀이

문제 자체는 간단하나, 풀이 방법이 신박해서 글을 작성하게 됐다.

처음엔 문제를 보고, 문자열을 내림차순으로 정렬하면 될까 싶었지만 그렇게 하면 문제에서 의도한 것과 같이 정렬이 되지 않는다.

• [3, 30, 34]를 문자열 내림차순 정렬시 [34, 30, 3]이 된다.
• 문제에 따르면 [34, 3, 30]이 되어야 한다.

 

그렇다면, 위에서 3이 30보다 앞에 오게 정렬을 어떻게 할 수 있을까?

그 방법이 바로 동일한 문자열을 늘리는 것이다. 예를 들어, 34는 3434, 3은 3333, 30은 3030과 같이 늘리고 문자열 내림차순 정렬을 하면, [3434, 3333, 3030]이 된다.

 

의도한 것과 같이 3이 30보다 앞에 오게 된다. 그렇다면 문자열을 얼마나 반복해서 늘려줄 것인가가 관건이다.

해당 문제에서는 numbers의 원소가 0 이상 1,000 이하라고 했으므로, 길이가 가장 긴 원소의 크기는 4가 된다. 따라서 4 이상만큼 문자열을 반복해서 늘려줘야 한다. 그리고 문자열의 길이가 동일하도록 잘라줘야 한다.

 

만약 그 이하로 크기를 늘려주게 되면, 문제의 의도와 같이 정렬이 되지 않는다.

• [1100, 1]이면 정렬 시 [1, 1100]이 되어야 한다.
• 만약 문자열을 3배만큼 늘려주게 된다면, [110011001100, 111]이 되고 문자열이 길이가 3가 되도록 잘라주고 문자열 내림차순 정렬하면 [110, 11]이 된다.
• 그렇게 되면 의도한 것과 다르게 정렬 결과가 [1100, 1]가 되게 된다.

 

따라서 4배로 문자열을 잘라주고, 길이 4만큼 슬라이싱 해줘야 한다.

처음에 대충 풀다가 3으로 잘라서 '틀렸습니다'가 나왔다.

def solution(numbers):
    answer = ''
    
    numbers = list(map(str, numbers)) # str로 변경
    numbers.sort(key=lambda x:(x*4)[:4], reverse=True)
    answer = int(''.join(numbers))
    
    return str(answer)

 

 

2️⃣ JAVA 풀이

JAVA는 compareTo()에 대한 이해가 있다면 쉽게 풀 수 있다. 

compareTo()에 대해 잘 모른다면 하단의 글을 참고하자.

[JAVA] compareTo()에 대해 알아보자(문자열, 숫자 비교)

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        String[] arr = new String[numbers.length]; // numbers를 문자열로 저장
        for(int i=0; i<numbers.length; i++){
            arr[i] = String.valueOf(numbers[i]);
        }
        
        // arr 정렬
        Arrays.sort(arr, (s1, s2) -> (s2+s1).compareTo(s1+s2));
        
        if(arr[0].equals("0")) return "0";
        
        for(String s:arr){
            answer += s;
        }
        
        return answer;
    }
}