[코딩 문제 풀이(파이썬/Python)] 프로그래머스 _ 가장 큰 수

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

코딩테스트 연습 - 가장 큰 수

[문제 설명]

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

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

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

 

[제한 조건]

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

답은 구할 수 있는 것 같지만 시간 초과된 코드.

# 시간 초과
def solution(answer):
    answer = list(map(lambda x: str(x), answer))
    answer = sorted(sorted(answer, reverse=True), 
                    key = lambda x : x[0], reverse = True)
    answer = sorted(answer, key = len, reverse = True)
    while sorting(answer) !=  answer:
        answer = sorting(answer)
    return answer
def sorting(numbers):
    num = numbers.copy()
    for i in range(len(numbers)-1):
        if len(numbers[i]) > len(numbers[i+1]):
            if numbers[i] + numbers[i+1] < numbers[i+1] +  numbers[i]:
                num[i:i+2] = numbers[i+1], numbers[i]
#     return num
    return int(''.join(answer)) == 0 and '0' or ''.join(answer)

통과한 코드.

# 통과한 코드
def sorting(numbers):
    num = numbers.copy()
    for i in range(len(numbers)-1):
        if len(numbers[i]) > len(numbers[i+1]):
            if numbers[i] + numbers[i+1] < numbers[i+1] +  numbers[i]:
                num[i:i+2] = numbers[i+1], numbers[i]
    return num
def solution(answer):
    answer = list(map(lambda x: str(x), answer))
    answer = sorted(answer, key = len, reverse = True)
    original = answer.copy()
    temp = [(x, y + y[0]*(4-len(y))) for x,y in enumerate(answer)]
    temp = sorted(temp, reverse = True, key = lambda x: x[1])
    answer = []
    for index, _ in temp:
        answer.append(str(original[index]))
    while sorting(answer) !=  answer:
        answer = sorting(answer)
    return int(''.join(answer)) == 0 and '0' or ''.join(answer)

핵심이 되는 테스트 케이스들은 아래와 같았다.

제일 간단한 풀이는 너무 허무하게 짧았다..

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

핵심은 숫자로 이루어진 문자열들의 비교 연산이었다.

예시에서 보이듯 문자열 간의 대소비교는, 맨 앞자리부터 차례로 각 문자의 아스키코드를 비교하게 된다. 맨 앞자리가 같은 경우, 그 다음 자리를 차례로 비교해주기 때문에 해당 문제에서 유용하다.

 

각 문자에 *3을 한다는 것은 다음과 같은 의미를 가진다.

ex1) 21 + 212 = 21212 < 212 + 21 = 21221 의 비교에서, 

212121 , 212212212 두 숫자를 비교했을 때 오른쪽이 크므로, 212가 선행해야 한다.

 

ex2) 12 + 121 = 12121 > 121 + 12 = 12112 의 비교에서,

121212 , 121121121 두 숫자를 비교했을 때 왼쪽이 크므로, 12가 선행해야 한다.

 

ex3) 1 + 10 = 110 > 10 + 1 = 101 의 비교에서,

111, 101010 두 숫자를 비교했을 때 왼쪽이 크므로, 1이 선행해야 한다.

 

즉, 핵심이 되는 자리 수가 다를 때의 비교가 가능한 모양을 str*3을 통해 간접적으로 만들어줌으로써 그들간의 비교 연산을 진행하는 것만으로 정렬을 마칠 수 있다. (자기 자신을 반복해서 붙였을 때 큰 숫자가 앞에 와야함)