[4코1파] #25. 가장 큰 수

gunny·2023년 1월 28일

4코1파 가장 큰 수 python 코딩테스트 코딩테스트 python 프로그래머스 가장 큰 수 프로그래머스 가장 큰 수 python

코딩테스트

목록 보기

25/530

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (25일차)
[4코1파] 2023.01.13~ (16일차)

Today :

2023.01.28 [25일차]

프로그래머스 LV2.
가장 큰 수
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 합니다.

입출력 예

※ 공지 - 2021년 10월 20일 테스트케이스가 추가되었습니다.

문제 풀이 방법

처음에는 itertools 의 조합과 순열 무새인 나는 또 순열로 풀었고, 시간초과로 탈락
알게 모르게 itertools 시간복잡도가 상당하나봄?

그래서 string 으로 바꾼 후에 정렬을 했는데,
3 이랑 30이랑의 배열에서 애를 먹어서 거의 1시간 쏟다가
이건 도저히 집에서는 머리가 안굴러 갈 것 같아서 구글링 했다
30분 고민했으니까 괜찮..지 않나?

암튼.. 3, 30을 비교하는 방법 중 기발했던 것은
위의 제한사항에서 문자열이 1,000 이하 이므로
1000이하에 맞추게 문자열 자체를 x3 해서 sort를 하면
3, 30의 매직이 풀린다는 거다
기존에 자꾸 정렬이 30,3 으로 되버렸던 것이
*3을 함으로써, 333, 303030 이 되면서 3, 30으로 정렬이 되는 것이다 !

내 코드

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

증빙