[Programmers-42746][Python] 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

 

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

문제 출처

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

프로그래머스

 

문제 해결 방법

• 문자열의 대소 비교 원리를 이해하면 풀 수 있었던 문제였다.
• 맨 처음에는 다음과 같이 순열(Permutation)을 이용하여 문제를 풀려고 하였으나, 시간 초과 오류가 떠서 더 심플한 방법을 찾아야 했다.

def solution_permutation(numbers):
    # 순서를 고려한 모든 수의 경우를 생각해야 하므로 순열(Permutation)을 사용할 것이다.
    from itertools import permutations 
    
    num_list = []
    
    nums_length = len(numbers)
    permutation_list = list(permutations(numbers, nums_length))    # nums_length 길이의 순열들을 리스트에 넣는다.
    
    for items in permutation_list:
        num_str = ''
        for item in items:
            num_str += str(item)
        num_list.append(int(num_str))
    
    num_list.sort(reverse=True)
    answer = str(num_list[0])

    return answer

 

• 숫자 문자열의 대소 관계는 문자열의 첫 글자부터 비교하여 결정된다. 숫자 문자열을 비교할 때, 다음과 같은 규칙이 적용된다.

1. 첫 번째 글자부터 비교한다.
2. 두 문자열의 첫 번째 글자가 다를 경우, 해당 글자의 아스키 코드 값에 따라 비교가 이루어진다.
- 아스키 코드 값이 낮을수록 작은 값으로 간주된다.
- 예를 들어 "342"는 "598"보다 작다.
3. 만약 두 문자열의 첫 번째 글자가 동일한 경우, 두 번째 글자를 비교하고 동일한 글자인 경우에도 다음 글자를 비교한다.
4. 이렇게 문자열의 모든 글자를 비교하여 두 문자열 중 하나가 먼저 끝나면, 길이가 짧은 문자열이 작은 값으로 간주된다.
- 예를 들어, "123"은 "1234"보다 작다.
5. 두 문자열이 동일한 모든 글자를 비교한 후에도 결과가 결정되지 않으면, 두 문자열은 동일한 값으로 간주된다.

 

• 문자열을 그대로 비교하는 방식으로 문제를 풀 수는 없다. 왜냐하면 4. 부분 때문이다. 두 번째 입력 예의 경우 @[3, 30, 34, 5, 9]@이며, 4. 규칙을 적용하여 내림차순으로 정렬할 경우 다음과 같다.

[9, 5, 34, 30, 3]

 

• 하지만 문제의 조건을 만족시키도록 하려면 다음과 같이 정렬되도록 해야 한다.

[9, 5, 34, 3, 30]

 

• 따라서 @3@이 @30@보다 더 크도록 정렬되게 하기 위해 @sort@ 함수의 @key@ 조건을 @lambda x: x * 4@로 설정해준다.
  • 이렇게 설정하면 @3@은 @3333@, @30@은 @30303030@이 되어 @3@이 @30@보다 더 앞쪽의 위치에 오게 된다.
  • 문제의 @제한 사항@에 "numbers의 원소는 0 이상 1,000 이하입니다." 라는 조건이 있으므로 한 자리의 숫자가 오는 경우를 생각해서 @x@의 값을 @x * 4@로 설정해준다.

numbers.sort(key=lambda x: x * 4, reverse=True)

 

코드

def solution(numbers):
    numbers = list(map(str, numbers))    # 각 int형 요소를 string형으로 변경
    numbers.sort(key=lambda x: x * 4, reverse=True)    # 내림차순 정렬
    
    if numbers[0] == '0':    # 모든 숫자가 0인 경우 0이 맨 앞에 오게 되므로 0으로 처리해준다.
        answer = '0'
    else:
        answer = ''.join(numbers)    # 리스트 안에서 정렬된 숫자들을 이어 붙이기
    
    return answer

 

• @key@는 정렬할 항목의 값을 변환하거나 가공하기 위한 함수를 지정하는 매개변수이다.
• @lambda x: x * 4@ : 각 문자열을 4번 반복하여 만든다.
  • 3 -> "3333"
  • 30 -> "30303030"
  • 34 -> "34343434"
  • 5 -> "5555"
  • 9 -> "9999"
  • 이렇게 하면 큰 숫자가 앞에 오도록 정렬된다. (9 -> 5 -> 34 -> 3 -> 30) 

 

참고

• 정렬