[프로그래머스] 가장 큰 수(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 합니다.

 

 입출력 예

 

 

 

 

 

풀이

 이 문제는 0 또는 양의 정수가 주어졌을 때, 해당 수들은 조합하여 만들 수 있는 가장 큰 수가 몇인지를 출력하는 문제입니다. 이 문제를 풀기 위해서  어떻게 정렬을 해야할지를 먼저 생각을 해보았습니다.

그래서 생각한 방법이 리스트를 문자열로 바꾸어 내림차순으로 정렬하는 방식이었고, 이 방식으로 풀이를 진행한 코드와 결과는 다음과 같습니다.

 

def solution(numbers):
    answer = ''
    
    numbers = list(map(str, numbers))               
    numbers.sort(reverse=True) 
    print(numbers)
    
    for i in numbers:           
        answer += i
    
    return answer

 

 

위와 같이 30과 3의 경우에 내림차순으로 정렬하면 30이 3보다 앞에 정렬되나, 실제 답은 '303' 의 순서가 아닌 '330'의 순서가 되어야 합니다.

이를 해결하는데 어려움을 많이 겪었고, 여러 풀이를 참고하였고, 참고하며 알게된 내용은 다음과 같았습니다.

먼저 30과 3, 39 라는 수가 있다고 가정합니다. 원하는 결과값을 얻기 위해서는 이 수들을 [39, 3, 30] 의 순서로 정렬이 되어야 합니다. 그러나 일반적인 내림차순으로 정렬할 경우에는 [39, 30, 3]의 순서로 정렬이 됩니다.

이 3개의 숫자를 비교하기 위해 자릿수를 맞추어주는 방법을 사용하면 어떻게 될까요? 3개의 수의 자릿수를 100 단위로 맞추어 한번 비교를 해보겠습니다. 자릿수를 맞추게 되면 [390, 300(30), 300(3)] 이 됩니다. 이를 다시 내림차순으로 정렬하더라도 [39, 30, 3] 의 순서로 정렬되므로 결과는 같아지게 됩니다.

그래서 이를 해결하기 위해 사용된 방법으로 위의 리스트의 수를 3번씩 반복하고, 그것을 비교하는 방법입니다.

이 방식으로 비교하게 되면 [393939, 303030, 333]이 되고, 이를 세자리 수까지 끊으면 [393, 303, 333]이 됩니다. 이렇게 되면 [393, 333, 303]순서로 내림차순이 가능해지고, 원래 수로 바꿔주면 [39, 3, 30] 의 순서가 됩니다.

위의 방식으로 풀이를 하면 문제에서 원하는 대로 정렬이 가능하고, 원하는 답을 얻을 수 있을 것입니다. 위의 내용을 토대로 정리를 다시 해보면 아래와 같을 것입니다.

 

1. 최초 numbers 리스트를 string으로 바꾸어준다. (숫자의 맨 앞자리부터 비교 가능)

2. 이후  numbers의 숫자를 3번씩 반복한 후, 그 수를 기준으로 내림차순 정렬을 한다. 

3. 정렬된 수를 0번째부터 순서대로 answer에 더해준다.

 

정리한 내용을 토대로 작성한 소스코드는 아래와 같습니다.

def solution(numbers):
    answer = ''
    
    numbers = list(map(str, numbers))               # string으로 바꾸어서 비교
    numbers.sort(key = lambda x : x*3,reverse=True)  # 3번씩 반복하면 붙였을때 큰수 찾기 가능
    
    for i in numbers:             # 정렬된 리스트를 answer에 순서대로 더해줌
        answer += i
    
    return answer

 

 이렇게 풀이하면 당연히 정답일줄 알았지만.....

 

 왜인지 테스트케이스를 딱 하나만 통과하지 못했습니다. 그렇게 한참을 고민하던 중 만약 리스트가 [0, 0] 인 경우라면 어떤 결과 값이 나올지를 생각해보았습니다. 이 경우 정답은 0이 되어야 하지만, 아마도 위의 코드로 풀게 되면 '00'이 나올 것으로 예상하고 테스트케이스를 하나 추가하여 테스트를 해보았습니다.

 

테스트를 진행해보니 위와 같이 '00'이 리턴되는 것을 확인할 수 있었습니다. 이를 고려해서 바꾼 풀이는 다음과 같습니다.

 

def solution(numbers):
    answer = ''
    
    numbers = list(map(str, numbers))               # string으로 바꾸어서 비교
    numbers.sort(key = lambda x : x*3,reverse=True)  # 3번씩 반복하면 붙였을때 큰수 찾기 가능
    
    for i in numbers:             # 정렬된 리스트를 answer에 순서대로 더해줌
        answer += i
    
    return str(int(answer))

 

위의 코드와 같이 리턴값을 한번 int로 바꾸어 준 후에 다시 string으로 바꾸어주었고, 모든 테스트케이스를 통과한 것을 확인할 수 있습니다.