[프로그래머스] '가장 큰 수' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

 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"

알고리즘 분석

 

• Most 1의 풀이

def solution1(numbers):
    numbers = list(map(str, numbers)) # numbers의 모든 요소를 str형으로 변경
    # numbers를 정렬한다. 이 때, 정렬 기준은 요소들을 3곱한 값이 가장 큰 수부터 정렬된다. 
    numbers = sorted(numbers, key=lambda x: x*3, reverse=True) 
    # 정렬된 값들을 문자열로 묶은 뒤, 정수형을 거쳐 다시 문자열로 변경
    answer = str(int(''.join(numbers)))  
    return answer

이 풀이는 약간의 꼼수(?)랄까. 파이썬 문자열의 특징을 잘 이용한 풀이다.

 

파이썬의 문자열은 다음과 같은 특징이 있다. 

 

• 두 문자열 중 첫 글자가 큰 문자열이 더 큰 문자열이다. 
• 두 문자열의 첫 글자가 같을 경우 그다음 글자가 큰 문자열이 더 크다.
• 위의 경우에서 한쪽의 문자열이 끝난 경우는 그 문자열이 더 작다. 

예시는 다음과 같다. 

 

• "9" > "34" : True 
• "9" > "59" : True 
• "3" > "30" : False
• "33" > "3030" : True

만약 위의 세 번째 예시가 True였다면 정렬 기준을 "lambda x: x*3"로 해주지 않았어도 정답이 나왔을 것이다. 

하지만 False이기 때문에 "30"이 "3"보다 앞에 오게 되었다. "330"이 "303"보다 크지만 정렬된 결과 "303"이 나오게 된 것이다. 이것이 x*3을 해준 이유이다. 

 

4번째 예시를 보면 같은 값에 곱하기 2를 했을 뿐인데 True가 나온 것을 볼 수 있다. 

 

위의 문자열 특징 중에 2번째 특징 때문에 가능한 것!

 

마지막에 join으로 만들어진 문자열을 굳이 정수형을 거쳐 문자열로 되돌린 이유는 '000000' 같은 값을 '0'으로 바꿔주기 위함이다. 

 

 

• Most 2의 풀이

# cmp_to_key를 이용한 간결한 풀이 
import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2))

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

 

Most 2가 출재자의 의도에 맞는 풀이인 것 같다.

 

cmp_to_key를 이용해서 리스트의 정렬 기준을 직접 만들어주었다. 

그 외에는 Most1과 동일