Level 2 가장 큰 수 Python3

https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3 

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

 

최종 풀이

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_가장큰수.py

hwayeon351/Programmers-Algorithms

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

---

풀이 과정

다시 한 번 풀어본 문제인데 막혀서 이전에 푼 코드를 살짝 확인해서 풀었다.

먼저, 각 numbers 항목에서 앞자리 숫자가 가장 큰 수부터 앞에 붙여나가야 하는 것을 떠올렸다.

이때, 앞자리 숫자가 같고 자릿수가 다른 경우를 어떻게 처리해야 할 지가 떠오르지 않았다.

예를 들어 3, 30, 34가 있는 경우, answer = 34330이 나와야 한다. 두번째 자리 수를 비교해서 34를 가장 앞에 붙이고 그 다음 두째 자리가 없는 경우와 두째 자리가 0인 경우는 없는 경우를 택해야 한다는 것은 떠올렸다. 하지만 이를 구현하는 것에 막혔다..

 

문제에 힌트가 나와있었는데, 바로 numbers의 원소는 1000이하의 숫자라는 점이다. 따라서 모든 원소를 3~4자리 수 이상으로 표현한 후, 각 자릿수를 탐색해서 큰 수부터 차례대로 붙여나가면 된다.

이때, 앞에서 말한 것처럼 3과 30의 경우, 3을 먼저 선택할 수 있도록 하기 위해 각 자리 수에 000을 붙이는 것이 아닌 해당 값을 3번 이어 붙이는 방법을 이용하면 된다.

즉, 3 -> 333, 30->303030으로 표현하면 앞자리 수부터 탐색했을 때, 2번째 자리 수에서 3이 0보다 크기 때문에 3을 선택해서 먼저 정답에 붙여주는 것이다.

 

이를 코드로 표현하면 다음과 같다.

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

#앞자리부터 차례대로 큰 수부터 정렬
#1000이하의 숫자이기 때문에 4자리 문자열로 변경하여 탐색
#numbers가 2개이상의 0으로만 주어지는 경우 000이 출력되는 것을 방지하기 위해
#list->str->int->str로 변환
#시간복잡도 = O(nlogn), 공간복잡도 = O(n)

1. numbers의 int형 원소들을 모두 str형으로 바꿔준다.

 list(map(str, numbers))

 

2. 모든 원소를 3~4자리 수 이상으로 표현한 x*3을 기준으로 내림차순으로 정렬한다.(이때, 정답 순서대로 리스트가 정렬된다.)

 sorted(list(map(str,numbers)), key=lambda x:x*3, reverse=True)

 

3. 정렬된 리스트를 str로 바꾼다.

''.join(sorted(list(map(str,numbers)), key=lambda x:x*3, reverse=True))

 

4. 3.의 결과를 다시 int형으로 변환한 다음, 한 번 더 str로 바꿔준다.

 이 부분이 주의해야하는 부분이다. numbers가 둘 이상의 0으로만 구성되어 있는 경우 3.까지만 진행하면 정답은 0000이 된다. 따라서 이 경우를 처리하기 위해 int형으로 변환하여 0000을 0으로 바꿔주고 다시 str로 바꿔줘야 한다.