[프로그래머스 Lv.2] 가장 큰 수 (정렬)

1. 문제 설명

• 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
• 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
• 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

2. 제한사항

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

3. 입출력 예

numbers	return
[3, 30, 34, 5, 9]	"9534330"

4. 문제 해결

• 빈 문자열로 수를 초기화

• 가장 크게 만들 수 있는 수를 고름
  => 수의 목록을 크게 만드는 것 우선으로 정렬하면 더 나음

• 그 수를 현재 수에 이어 붙임

• 모든 수를 다 사용할 때까지 반복함

  O(nlogn)

• 크게 만드는 수의 기준 찾기

  3 vs 32 = 332 > 323 => 3
  3 vs 33 = 333 = 333 => 아무거나
  3 vs 34 = 334 < 343 => 34
  34 vs 342 = 34342 > 34234 => 34
  34 vs 343 = 34343 > 34334 => 34
  34 vs 344 = 34344 < 34434 => 344

  • 34 => 3434|343434..
    vs
    343 => 3433|43343..
    => 앞에 4개만 끊어서 비교하면 됨

• 이렇게 대소 관계 비교를 위한 기준을 마련하고 이를 이용해서 주어진 배열을 정렬하면 그 배열을 이용해서 문자열 표현을 완성할 수 있음

파이썬 풀이(1)

def solution(numbers):
    numbers = list(map(str, numbers)) # 문자로 변경
    # 문자열을 4번 반복하도록 하고 앞에서 4개까지만 slice함
    numbers.sort(key=lambda x : (x * 4)[:4], reverse = True) 
    if numbers[0] == '0': # 0으로만 이루어진 경우에는 그대로 0을 리턴
        return '0'
    else:
        answer = ''.join(numbers) # 문자열을 이어 붙임
    return answer

• 리스트의 값을 모두 문자로 만드는데 numbers 크기에 비례한 시간이 걸림 : O(n)
• 리스트를 정렬하는 것은 n*logn만큼의 시간이 걸림 : O(nlogn)
• join은 numbers 크기에 비례한 시간이 걸림 : O(n)
• 전체 시간 복잡도는 정렬에 의해 결정됨 : O(logn)

파이썬 풀이(2)

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x : x * 3, reverse = True)
    return str(int("".join(numbers)))

• int형 list를 str형 list로 변환
• numbers의 원소는 1000 이하이기 때문에 3자리수로 맞춰서 비교 수행
• 모든 값이 0일 경우에는 반복되는 0을 제거하고 0만 반환해주기 위해서 str를 int로 변환하여 00과 같은 형태를 0으로 변환해준 후 다시 str로 변환해서 반환함

자바 풀이

import java.util.*;

class Solution {
    public String solution(int[] numbers) {     
        String[] nums = new String[numbers.length];
        
        // int형 배열을 String형 배열로 바꿈
        for(int i = 0; i < numbers.length; i++){
            nums[i] = Integer.toString(numbers[i]);
        }
        
        // 내림차순 정렬 : 두 수를 합해서 합이 가장 큰 경우로 두 수를 정렬함
        Arrays.sort(nums, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2){
                return (o2+o1).compareTo(o1+o2);
            }
        });
        
        // 0이 중복인 경우 0만 반환
        if(nums[0].equals("0")){
            return "0";
        }
        
        return String.join("", nums);
    }
}