[프로그래머스] 가장 큰 수 (코딩테스트 연습 | 정렬)

⭐️ 0. 문제

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

프로그래머스

 

---

⭐️ 1. 아이디어

✅ 1. 자릿수를 전부 맞추고 비교

[1, 22, 23] -> [11, 22, 23]으로 전체 숫자의 자릿수를 맞춤.
단, 이때 길이의 max로 자릿수를 맞추는 게 아니라 길이의 최소공배수로 자릿수를 맞춤
[11, 222] -> [111111, 222222]

 

✅ 이 아이디어가 올바른 이유

 

case 1 : 5 51 -> 551

case 2 : 5 58 -> 585

 

이 두 케이스를 보았을 때, 5 vs 51의 경우 5가 크다.

하지만 5 vs 58의 경우 58이 더 크다.

 

즉, 5 vs 5X 의 경우, X가 5보다 크다면 5X가 큰 것이다.

그렇다면 55 vs 5X로 숫자를 바꾸고 비교를 진행해도 될 것이다.

case 1 : 5 51 -> 55 51 -> 551

case 2 : 5 58 -> 55 58 -> 585

---

 

case 3 : 133 1331 -> 1331331

 

이 케이스를 살펴보자.133 -> 길이 31331 -> 길이 4이때, 길이를 4로 맞춘다면 1331 vs 1331. 즉, 숫자는 같다. 비교가 불가한 것이다!(하지만 분명히 답은 1331331이다.)

 

길이 3, 길이 4의 최소공배수인 12로 숫자를 늘리자.

[A] 133 133 133 133 (정답)

[B] 1331 1331 1331

-> 비로소 A가 B보다 큰 것을 알 수 있다.-> 즉, 1331 1331이 정답인 것이다.

 

---

✅ 2. 두 원소씩 비교 시, 앞으로 붙이고 뒤로 붙여 비교

[1, 12, 23] 비교 시
1 vs 12 -> 112 , 121 -> 121

1 vs 23 -> 123, 231 -> 231

12 vs 23 -> 1223, 2312 -> 2312

 

✅ 이 아이디어가 올바른 이유

 

앞으로 붙이고 + 뒤로도 붙여 대소를 비교한다.

이렇게 하면 어떤 경우에 가장 큰 수를 만들 수 있는지를 바로 알 수 있기 때문이다.

(아이디어는 심플하다)

 

---

⭐️ 2. 코드

✅ 1. 자릿수를 전부 맞추고 비교

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    len_numbers = list(map(lambda x : len(x), numbers))
    
    # 최소공배수
    def lcm(lengths):
        answer = lengths[0]
        
        for length in lengths:
            if answer % length == 0:
                continue
            else:
                answer = answer * length
        
        return answer
    
    max_len = lcm(len_numbers)
    new_numbers = []
    
    # 기존 숫자들을 -> max_len 길이만큼 늘림
    for num in numbers:
        count = 0
        original_len = len(num)
        while len(num) < max_len:
            num = num + num[count%original_len]
            count += 1
        new_numbers.append(num)
        
    # new_numbers 정렬 후 이어붙임
    
    # 인덱스 구하기 (gpt)
    index = sorted(range(len(new_numbers)), key=lambda i : new_numbers[i], reverse=True) 
    # key 함수의 인자 = range(len(new_numbers))
    answer = ''.join([numbers[i] for i in index])
    
    # 0000 -> 0
    while answer[0] == '0' and len(answer) > 1:
        answer = answer[1:]
    return answer

 

 

✅ 2. 두 원소씩 비교 시, 앞으로 붙이고 뒤로 붙여 비교

from functools import cmp_to_key

def solution(numbers):
    # int -> str
    numbers = list(map(str, numbers))
    
    def compare_custom_func(a, b):
        # 주의: a, b 는 str임
        cmp1 = a+b
        cmp2 = b+a
        if cmp1 > cmp2:
            return -1 # 음수 -> 앞의 것이 우선순위가 높다 (오름차순 정렬이 기본이므로)
        elif cmp1 == cmp2:
            return 0
        else:
            return 1
    
    numbers.sort(key=cmp_to_key(compare_custom_func))
    answer= ''.join(numbers)
    
    # 0000 -> 0
    while answer[0] == '0' and len(answer) > 1:
        answer = answer[1:]
    return answer