99클럽 코테 스터디 11일차 TIL, 프로그래머스 / 가장 큰 수

🔑 오늘의 학습 키워드 : 정렬

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/42746

 

from functools import cmp_to_key

def solution(numbers):
    answer = ''
    # 두 숫자를 바꿔야하는지 여부
    def to_swap(x,y):
        if str(y)+str(x)>=str(x)+str(y) : return 1
        else : return -1
    numbers.sort(key = cmp_to_key(to_swap))
    return str(int(''.join(map(str,numbers)))) # [0,0]이 주어지는 경우 대비해서 str(int())

시간 초과 풀이

def solution(numbers):
    answer = ''
    
    # 두 숫자를 바꿔야하는지 여부
    def to_swap(x,y):
        return str(x) + str(y) < str(y) + str(x)
    
    for i in range (1, len(numbers)):
        j = i
        while j > 0 and to_swap(numbers[j-1],numbers[j]):
            numbers[j-1] , numbers[j] = numbers[j] , numbers[j-1]
            j -= 1
    
    return str(int(''.join(map(str,numbers)))) # [0,0]이 주어지는 경우 대비해서 str(int())

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

문제는 두 숫자를 비교하면서 제일 큰 숫자를 만드는 것이 목표이다.

 

예를 들어 3, 30이 330이 되냐 303이 되냐를 결정해주는 문제이다.

 

그렇다면 두 숫자를 문자열로 합친 후 비교하면서 정렬하면 되겠다

 

⏰ 예상 시간 복잡도 O(N^2) -> 시간 초과 5 * 10 ^9

제한 사항

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

 

-> 다른 정렬 방법을 찾아보던 파이썬 내장 함수의 정렬을 사용하던 해야겠다.

 

😎 알고리즘 개요

https://docs.python.org/ko/3/howto/sorting.html#sortinghowto

Comparison Functions
Unlike key functions that return an absolute value for sorting, a comparison function computes the relative ordering for two inputs.

For example, a balance scale compares two samples giving a relative ordering: lighter, equal, or heavier. Likewise, a comparison function such as cmp(a, b) will return a negative value for less-than, zero if the inputs are equal, or a positive value for greater-than.

It is common to encounter comparison functions when translating algorithms from other languages. Also, some libraries provide comparison functions as part of their API. For example, locale.strcoll() is a comparison function.

To accommodate those situations, Python provides functools.cmp_to_key to wrap the comparison function to make it usable as a key function:

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

비교 함수
정렬을 위해 절대값을 반환하는 키 함수와는 달리, 비교 함수는 두 입력에 대한 상대 순서를 계산한다.

예를 들어, 균형 척도는 상대적인 순서를 제공하는 두 표본을 비교한다: 더 가볍다, 같다, 또는 더 무겁다. 마찬가지로, cmp(a, b)와 같은 비교 함수는 입력이 같으면 -보다 작으면 음의 값을, 0이면 -의 값을, 또는 -보다 크면 양의 값을 반환한다.

다른 언어에서 알고리즘을 번역할 때 비교 함수를 접하게 되는 것이 일반적이다. 또한 일부 라이브러리는 API의 일부로 비교 함수를 제공한다. 예를 들어 local.strcoll()은 비교 함수이다.

이러한 상황을 수용하기 위해 파이썬은 functools.cmp_to_key를 제공하여 비교 함수를 키 함수로 사용할 수 있도록 한다:

sorted(단어, key=cmp_to_key(strcol)) # 로케일 인식 정렬 순서

 

-> 정렬 조건을 return a-b으로 a-b가 양수면 오름차순 , 음수면 내림차순으로 설정한다.

 

이를 바탕으로 to_swap 함수를 이렇게 바꿔서 원하는 조건을 적용할 수 있다.

def to_swap(x,y):
    if str(y)+str(x)>=str(x)+str(y) : return 1
    else : return -1

sort()와 sorted()의 차이가 있는데 주로 sort()가 더 빠르다.

이유 보러가기 : https://codekunst.tistory.com/104

그래서 재사용 할일이 없다면 주로 sort()를 쓰는 편이다.

 

✅ 오늘의 회고

- cmp_to_key에 대해 알 수 있었다.

- 지난번에 사용했던 reduce()함수 또한 functools에 있었는데 Javascript에 있는 함수를 쓸 수 있는 것 같다.

  reduce()함수 보러가기 : https://codekunst.tistory.com/110

- functools에 있는 함수들을 많이 알아둬야겠다

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL