99클럽 코테 스터디 7일차 TIL + 정렬:가장 큰 수

문제

링크텍스트

풀이

• 2기 도중 푼 문제 중에 제일 어려웠습니다.
• 남아 있는 후보군 중에 첫 숫자가 가장 큰 수가 여러 개이고 그들의 자릿수가 서로 다른 경우가 문제였습니다.
  • 자릿수가 같다면야 첫 수자, 다음 숫자, 이렇게 차례로 비교하면 끝이지만, 비교해야 하는 자릿수가 부족한 경우가 발생하면 다른 후보군을 이어 붙여서 비교해야 하는데, 결국 경우의 수가 커지면서 코딩하기가 복잡해 집니다.
  • 그런데, 우선 첫 숫자가 같지 않은 후보들은, 그들의 첫 숫자는 더 작을 것이기 때문에, 굳이 이어 붙일 후보 중의 하나로 고려할 필요가 없었습니다. 첫 숫자가 같은 후보만으로 충분한 것이죠.
  • 그렇다면 첫 숫자가 같은 후보들만 서로 이어 붙이는 경우를 고려해 주면 되었습니다.
  • 그 경우에는 비교하는 양측을 서로 이어 붙인 것을 비교하면, 예컨대 x와 y를 비교할 때, x+y와 y+x를 비교하면 되었습니다.

결과

def f_t(id_t):
    if id_t == 0:
        numbers, r = [6, 10, 2],	"6210"
    elif id_t == 1:
        numbers, r = [3, 30, 34, 5, 9],	"9534330"        
    return numbers, r

# import heapq
import functools
def compare(x,y):
    return int(y+x) - int(x+y)
    
def solution(numbers):
    n = len(numbers)
    nN = list(map(str, numbers))
    nN.sort(key=functools.cmp_to_key(compare))
    return str(int(''.join(nN)))

for i in range(2):
    print(f'test case {i}')
    numbers, r = f_t(i)
    a = solution(numbers)
    print(a)
    print(r)