[프로그래머스/Python] 알고리즘고득점Kit-정렬-가장 큰 수

📌 문제 링크

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 합니다.

 

 📌풀이 과정 

• <처음 시도> 실패 

l = list(permutations(numbers, n_len)) 선언 후
...
for i in range(len(l)): 
	tmp=list(map(str, l[i]))
	tmp.sort(key=lambda x:x[0][0][0], reverse=True)

 
=> 위와 같이 작성하면

• [6, 10, 2]의 경우 각 요소에 대해 '6', '1', '2'끼리만 sort 되어 [6, 2, 10]으로 이 testcase는 통과가 되지만
• [3, 30, 34, 5, 9]의 경우 각 요소에 대해 '3', '3', '3', '5', '9' 끼리만 sort되어 [9, 5, 3, 30, 34], [9, 5, 30, 3, 34], [9, 5, 34, 30, 3] 이렇게 3가지만 생기게 된다. 
• 이랬을 때 중복되지 않게 tmp_list에 추가해 가장 큰 값을 골라내 join()하면 될거라 생각했다. 

=> 문제는 너무 오래 걸린다는 점..
 
✅ 결국 내가 원하는 것은 [3, 30, 34]를 정렬할 때 [34, 3, 30]의 순서를 원하는 것이다. 
이것에 대해 해결하고자 고민하다가 결국 구글링을 해서 알아낸 점은, (아래에) 
 

✅ [제일 중요] [3, 30, 34]에 대해서 

1. 각 요소를 문자열로 바꾼다. => ['3', '30', '34']
2. 해당 요소를 각각 3번씩 반복시킨 문자열로 만들면 ['333', '303030', '343434'] 이랬을 때 3자리까지만 본다면 ['333', '303', '343']이 된다. 이를 정렬해보자 => ['343', '333', '303']으로 원래 요소라면 [34, 3, 30]으로 정렬됨을 알 수 있다. 

이를 코드로 나타내면 아래와 같다. <출처: https://liveloper-jay.tistory.com/138 진짜 대단하신듯하다..>

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

 
++ 테스트 케이스 [0,0]에 대해서 0이 나와야 하는데 '00'이 나오게 된다. 이를 위해 return 할 때 int로 바꿨다가 str로 바꿔주는 작업이 필요하다. 
 

 📢여기서 포인트

숫자 배열을 정렬해 큰 수를 만들어야 할 때, 각 요소를 n번 반복시켰을 때의 값으로 정렬하는 것도 방법이다.
 

📌 풀이 코드

from itertools import permutations
def solution(numbers):
    answer = 0 
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x:x*3, reverse=True)
    # print(numbers)
    return str(int(''.join(numbers)))
##########################################################
# 시간 초과 코드
# def solution(numbers):
#     answer = ''
#     n_len = len(numbers)
#     l = list(permutations(numbers, n_len))
#     tl = []
#     for i in range(len(l)): 
#         tmp=list(map(str, l[i]))
#         tmp.sort(key=lambda x:x[0][0][0], reverse=True)
#         if tmp not in tl: tl.append(tmp)
#     for t in range(len(tl)):
#         tl[t] = ''.join(tl[t])
#     answer = str(max(tl))
#     return answer