[프로그래머스] 가장 큰 수 / 파이썬

가장 큰 수

문제 설명

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"

풀이

• 기존에 했던, 최강의 패와 동일한 문제
• permutations을 이용해서 완전탐색을 할 경우 시간초과 발생
• QuickSort를 이용해서 우선순위가 높은 값부터 사용

def myQuickSort(nums, l, r):
    if l >= r:
        return 

    # pos를 진행하면서 l에서 r까지의 범위가 정렬이 됨 (우선순위 가장 작은게 맨 뒤로 감)
    # pos는 nums에서 가장 우선순위가 작은 값 
    pos = partition(nums, l, r)

    # QuickSort는 pos(우선선위가 가장 작은 값)
    myQuickSort(nums, l, pos-1)
    myQuickSort(nums, pos+1, r)

def partition(nums, l, r):
    # print(nums, l, r)
    low = l
    while l < r:
        # l + r > r + l 이면 
        if compare(nums[l], nums[r]):
            nums[l], nums[low] = nums[low], nums[l]
            low += 1

        l += 1

    # 가장 낮은 순위 low를 가장 오른쪽 r과 변경 
    # 여기서 r은 분할정복으로 들어왔기에 들어온 값중에서 마지막임 
    nums[low], nums[r] = nums[r], nums[low]
    return low

def compare(n1, n2):
    return str(n1) + str(n2) > str(n2) + str(n1)

def solution(numbers):
    myQuickSort(numbers, 0, len(numbers)-1)
    answer = str(int("".join(map(str, numbers))))
    return answer

다른사람 풀이

• 문제의 numbers의 원소는 0 이상 1,000 이하입니다. 라는 조건을 통해서 numbers.sort(key=lambda x" x*3, reverse = True)를 해서 정렬
• [6, 10, 2]을 예시로 들면, numbers.sort(key=lambda x" x*3, reverse = True)를 하면,
  • [666, 101010, 222]가 되고 이를 정렬하면, [666, 222, 101010]이 되어서 결과적으로 [6, 2, 10]의 순서가 된다.
  • 위와 같이 정렬되는 이유는 박상희님의 댓글에 따르면 "문자열 비교연산의 경우엔 첫번째 인덱스인 666[0]인 6과 101010[0]인 1과 222[0]인 2를 ascii숫자로 바꿔서 비교합니다. 물론 같으면, 다음 인덱스도 비교합니다. 비교한 결과 [6, 2, 10]의 순으로 정렬됩니다."
  • 즉, 앞자리가 큰 6 -> 2 -> 1순으로 정렬되어서 위와 같은 결과를 얻게 된 것입니다.

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

• 저와 같은 풀이인데, 코드는 훨씬 간단하여 올립니다.

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

 

출처: 프로그래머스 코딩 테스트 연습,https://programmers.co.kr/learn/challenges