[프로그래머스] 가장 큰 수

 

 

 

 

https://school.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 합니다.

 

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

---

분명 풀었던 문제 같은데.. 파일을 뒤져보니 역시나

Coursera에서 USCD의 algorithmic-toolbox를 들을 때, 3주차 과제로 했던 문제였다.

(https://github.com/kimwoolina/algorithmic-toolbox/blob/main/week3_7.py)

문제 풀이

import functools

def custom_compare(n1, n2):
    num1 = str(n1)
    num2 = str(n2)
    return int(num1 + num2) - int(num2 + num1)

def solution(numbers):
    # 숫자들을 정렬
    sorted_numbers = sorted(numbers, key=functools.cmp_to_key(custom_compare), reverse=True)
    
    # 결과 조합
    largest = "".join(map(str, sorted_numbers))
    
    return largest

 

여기 까지 했는데 11번째 테스트 케이스에서 에러가 났다.

 

알고보니 리스트의 모든 값이 0으로 주어지는 경우,

기존 코드에서는 [0,0,0] ➡️ "000" 이런 식으로 출력이 되어, 이럴 경우 "0"으로 출력 되도록 하는 과정이 필요했다.

 

완성코드

# 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수

import functools

def custom_compare(n1, n2):
    num1 = str(n1)
    num2 = str(n2)
    return int(num1 + num2) - int(num2 + num1)

def solution(numbers):
    # 숫자들을 정렬
    sorted_numbers = sorted(numbers, key=functools.cmp_to_key(custom_compare), reverse=True)
    
    # 결과 조합
    largest = "".join(map(str, sorted_numbers))
    
    # 모든 숫자가 0인 경우 처리
    if largest[0] == '0':
        return '0'
    
    return largest


# test
print(solution([0, 0 ,0, 0 ,0 ,0])) # "0"
print(solution([6, 10, 2]))	# "6210"
print(solution([3, 30, 34, 5, 9]))	# "9534330"

 

---

다른 풀이

def custom_compare(n1, n2):
    num1 = str(n1)
    num2 = str(n2)
    # 문자열 조합을 비교하여 순서를 결정
    if num1 + num2 > num2 + num1:
        return -1
    elif num1 + num2 < num2 + num1:
        return 1
    else:
        return 0

functools.cmp_to_key는 실제로는 어떤 정수값을 반환해도 양수,0,음수 별로 작동하지만,

사실 더 명확히는, 비교함수가  -1, 0, 1을 반환하도록 기대한다.

 

또한 이 문제에서는 정수의 범위가 주어졌지만,

정수값이 너무 커질 경우 정수의 범위를 벗어날 수 있기 때문에

 

custom_compare 함수를 이렇게 작성해주면 더 정확하다.

---

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

마찬가지로 sort, key 를 사용하였는데

 

s = ['9', '66', '6', '60', '22', '2', '10'] 일 경우,

s[0]*3 -> '999' s[1]*3 -> '666666' s[2]*3 -> '666' s[3]*3-> '606060'

를 이용하여 정렬하는 방법을 사용했다.

 

문자열은 아스키값으로 치환되서 정렬되기 때문에 첫번째 인덱스값으로 비교를 하므로

666,101010,222 여기서는 아스키값으로 보면 1: 81, 2: 82, 6:86 이기 때문에 위와 같은 결과가 나온다.

 

입력 숫자가 1,000 이상인 경우에는 (x*3)이 충분하지 않을 수 있다.

하지만, 문제의 제약 조건에서는 1,000 이하의 숫자만을 처리하기 때문에 가능한 풀이이고

위 방법이 더 정확한 것 같다.

---

관련 문법 정리

sorted(key= ), sort(key= )

내림차순

reverse = True ➡️ 기존 오름차순 정렬을 reverse 하겠다. (즉, 내림차순됨)

 

절댓값

key = abs ➡️ 절댓값을 기준으로 정렬하겠다.

my_list = [-5, 3, -1, 0, 2, -4]
sorted_list = sorted(my_list, key=abs, reverse=True)

# [-5, -4, 3, 2, -1, 0]

 

문자열을 길이를 기준으로 정렬

key의 기준을 문자열의 길이 즉, key = len을 넣어주면 문자열의 길이를 기준으로 짧은 순서대로 정렬할 수 있다.

my_list = ["api", "app", "carrier", "demon", "aaa"]
sorted_list = sorted(my_list, key=len)
print(sorted_list)

# ['api', 'app', 'aaa', 'demon', 'carrier']

---

두개의 조건으로 비교하고 싶은 경우: lambda 사용

key에는 한개의 비교조건만 적용 가능한데,

두개의 조건을 한번에 비교해야하는 상황에는  lamda 함수를 통해서 이를 마치 하나의 비교조건인 것처럼 묶어서 사용한다.

길이를 기준으로 정렬하고, 오름차순(사전순)으로 정렬

첫번째로 나온len(x)를 통해 길이 순서로 정렬하되,
만약에 같은 길이가 나온다면, 두번째 비교 방법인x를 통해서 오름차순(사전순)정렬하라는 뜻

my_list = ["api", "app", "carrier", "demon", "aaa"]
sorted_list = sorted(my_list, key= lambda x : (len(x), x))
print(sorted_list)

# ['aaa', 'api', 'app', 'demon', 'carrier']

---

cmp_to_key()

.sort()나 sorted()를 사용할 때 그 안에서 정렬조건으로 넣는 key에  lambda뿐만이 아니라 

functools.cmp_to_key(custom_compare)를 사용하여 custom_compare를 키 함수로 변환해

sorted 함수를 나만의 조건으로 정렬할 때 사용할 수 있다.

 

cmp_to_key 함수는 Python의 비교 함수(cmp 스타일)를 키 함수(key 스타일)로 변환하는 데 사용됩니다.

Python 2에서의 cmp 함수를 Python 3에서의 key 함수와 호환되게 만들어준다.

 

이 때, 일반적으로 사용하는 비교함수 compare()은 다음과 같다.

def compare(x, y):
    if x+y > y+x:
    	return -1
    elif x+y == y+x:
    	return 0
    else:
    	return 1

 

Python의 정렬 알고리즘은 이러한 반환 값을 기반으로 객체를 정렬하기 때문에, 비교 함수가 정확히 -1, 0, 1을 반환하는 것이 일반적이지만, 사실 cmp_to_key를 뜯어봐도 알 수 있듯이 양수, 0, 음수면 작동한다.

 

custom compare 함수의 리턴값에 따른 정렬 방식

return 음수 : 먼저 들어온 요소가 앞으로 정렬됨
return 0 : 바뀌지 않음
return 양수 : 나중에 들어온 요소가 앞으로 정렬됨(먼저들어온 요소보다 앞에 배치됨)

 

def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
    	# __slots__는 클래스의 인스턴스가 사용할 수 있는 속성을 정의합니다. 
        # 여기서는 obj 속성만 사용하도록 제한합니다. 
        # 이로 인해 메모리 사용량이 줄어들 수 있습니다.
        __slots__ = ['obj']
        
        # 생성자 메서드
        # 객체가 생성될 때 obj를 초기화합니다. 
        # obj는 정렬할 객체를 저장
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K