[Python] 코딩테스트 고득점Kit | 정렬2-가장 큰 수

아래의 문제는 프로그래머스 코딩테스트 고득점 Kit 내용이며 코드는 직접 푼 내용입니다.

---

가장 큰 수  

문제상황

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

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210

 

요구사항

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때,

순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수

 

제한사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력

 

---

풀이과정

permutations를 통해서 numbers로 주어진 숫자들 중에서 만들수 있는 모든 수를 뽑으려고했다.

그리고 가장 큰수를 뽑을 생각이였다... 하지만 시간초과로 실패였다. 

나의 IDE에서 테스트해볼땐 결과는 같지만 실제로 프로그래머스에서는 실패로 떴다. 

 

 

결과

내가 푼 코드 - permutations (실패) 

하긴 생각해보면 조합으로 숫자를 뽑는게 너무 경우의 수가 많다.. 넘 무식했던 방법이다

실제로 문제 예시처럼 만들수 있는 수를 한번 print 해봤는데 그 수가 너무나도 많았다..

from itertools import permutations

def solution(numbers):
    answer =[]
    for i in permutations(numbers,len(numbers)):
        k=''.join(list(map(str,i)))
        answer.append(k)
    return max(answer)

이럴 경우 조합하는 시간은 O(len(numbers)!) 가 된다. 그래서 길이가 길 수록 시간이 오래걸리게 된다. 

 

정답

정답을 참고하고 리뷰해봤다. 여기에서 포인트는 '조건'에 있었다. 

• numbers의 원소는 0 이상 1,000 이하입니다.

그래서 1000이하의 숫자로 만들어서 비교하는 것이다. 

그래서 다음포인트는 '문자형'으로 정렬하는 것이다! 

문자형은 숫자형과 다르게 첫글자가 큰 순서대로 정렬되기 때문에 문자열의 길이가 긴 순서대로 크기 비교가 가능하다

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

그래서 문자형으로 비교하기 위해 

int형식으로 들어온 numbers를 str형식의 list로 map을 통해 바꾼다. # ['6', '10', '2']

 

그리고 정렬을 하는 key가 포인트이다.

lambda x:x:3  이말은  for i in numbers: print(i*3) 이 뜻인데 문자열3개씩 나열하는것이다.

그래서 ['666,'101010,'222']를 비교해서 sort를 한다고 한다.

즉, 1000이하의 숫자를 만들어서 비교하는 것과 같은 원리이긴 하지만 아직도 이해하기 어렵다..

 

그리고 역순으로 정렬하기 때문에 #['6','2','10'] 이 된다.

 

결국 이 순서대로 다시 문자열로 합쳐서 return하는 것이다. 

 

 

배운점

• 사실 어려웠다. 그래서 잘 모르겠는데 덕분에 lambda식을 배웠다. 
• 이런상황에선 어떻게 접근해야하는지 써야하는지

---

참고 

lambda식  https://free-eunb.tistory.com/71

정수를 모두 4자리수로 바꿔서 비교하는 포인트 https://jiwon-lee-it.tistory.com/58