[엘리스] 최강의 패

최강의 패

남녀노소 모두가 즐길 수 있는 코더랜드 고유의 전통 놀이가 있습니다. 이 놀이의 이름은 바로 수투!

수투를 즐기는 법은 간단합니다. 자연수로만 이루어진 카드 뭉치에서 일정한 수의 카드를 뽑아 최고로 큰 숫자를 만드는 사람이 이기는 방식입니다.

 

엘리스와 토끼, 체셔, 모자장수는 둘러앉아 게임 수투를 시작했습니다. 시간이 지나고 엘리스는 계속 지기만 하는 자기 자신을 마주할 수 밖에 없었습니다!

 

“엘리스 이 바보야. 넌 2, 10, 5 를 받았잖아 그럼 1052이 제일 큰 수가 아니라 5210이 제일 큰 수야.” 체셔가 말했습니다.

 

“아! 그렇구나.” 엘리스가 답했습니다.

 

이대로 가다간 엘리스는 한 판도 못 이기겠습니다. 여러분이 엘리스를 도와 최고로 높은 수를 찾아주세요!

입력 예시

5 2 52 100

출력 예시

5522100

입력

• 자연수로 이루어진 숫자(NumberNumber) 리스트가 주어집니다.
• 주어지는 NumberNumber의 길이는 1 ≤ NumberNumber ≤ 1,000 입니다.

출력

• 주어진 숫자(NumberNumber) 리스트로 조합 할 수 있는 숫자 중 가장 큰 숫자를 출력하세요.
• 숫자가 너무 커질 수 있으니 문자열 형태로 출력합니다.

풀이

• 완전탐색을 이용한 풀이

import itertools 

# 맨 앞자리가 가장 큰 값중에서 길이가 작은 순서대로 출력 
def main():
    A = list(map(str, input().split()))
    print(str(max(map(int, list(map(''.join, itertools.permutations(A)))))))
        
if __name__ == '__main__' : 
    main()

모범 답안 

• 완전 탐색의 경우 입력된 데이터의 크기가 너무 커서 에러가 발생할 수 있음 
• 모범 답안의 경우 compare라는 정렬 기준을 정해주고, quick sort로 분할해서 정렬 
  • nums[low] : nums 배열 중에서, 서열이 가장 낮은 것 
  • nums[l] : 맨 왼쪽에서부터 차례대로, 현재 가리키고 있는 수 
  • num[r] : 맨 오른쪽의 수 

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)

nums = input().split()
nums = [int(i) for i in nums]

myQuickSort(nums, 0, len(nums)-1)
print(str(int("".join(map(str, nums))))) 

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn