[알고리즘/프로그래머스] 가장 큰 수

정렬 > 가장 큰 수 / level2

코딩테스트 연습 - 가장 큰 수

나의 풀이

접근방법 1. permutations 사용
--> 문제점 : 시간 초과

접근방법 2. 문자열이 큰 순서대로 정렬하면 될 것
--> 문제점 : 3, 30이 있을 때 330이 아니라 303으로 정렬됨

접근방법 3. 문자열 정렬 비교 시 자릿수를 맞춰준다.
- 문자열 중 가장 큰 자릿수를 구해서 맞춰줌

 

import itertools

def solution(numbers):
    max_len = len(str(max(numbers)))
    str_list = [str(i) for i in numbers]
    str_list.sort(key = lambda x : x + (max_len - len(x)) * x[-1], reverse = True)
    return ''.join(str_list)

접근방법 4. 문자열 정렬 비교 조건 변경
- 문제 조건 중 numbers의 원소는 0 이상 1,000 이하 --> 비교가 필요한 최대 자릿수는 3
- 문자열 * 3 해준 문자열로 비교
(처음에 바보처럼 numbers의 길이는 1 이상 100,000 이하 조건으로 잘못 봐서 6을 곱해줌,, ㅎ ㅎ)

 

str_list.sort(key = lambda x : x * 3, reverse = True)

--> 0에 대한 처리 추가적으로 필요하여 코드 추가 ( [0, 0, 0]일 때 "000"으로 나오는 문제 발생 )

---

최종 제출 코드

 

import itertools

def solution(numbers):
    if set(numbers) == {0}:
        return "0"
    
    max_len = len(str(max(numbers)))
    str_list = [str(i) for i in numbers]
    str_list.sort(key = lambda x : x * 3, reverse = True)
    return ''.join(str_list)

---

다른 사람의 풀이
: 앞의 접근 방법4를 아주 깔끔하게 풀어두신 분의 코드

 

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