[코테리뷰] 정렬 - Lv2. 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

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

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.

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

• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	6210
[3, 30, 34, 5, 9]	9534330

코드 분석

처음 시도

• permutation을 사용해서 모든 경우의 수를 구했다.
• 결과: sample은 ok, test case는 전부 시간 초과가 나왔다..!

# 주어진 numbers에서 정수를 이어붙여서 만들 수 있는 가장 큰 수를 찾는다.
# 정수를 붙이는 순열 이용 => 그 중 가장 큰 수 찾기
from itertools import permutations


def solution(numbers):
    answer_list = []
    all_list=list(permutations(numbers,len(numbers)))
    for i in range(len(all_list)):
        temp=""
        for j in range(len(all_list[i])):
            temp = temp +str(all_list[i][j])
        answer_list.append(temp)
    print(answer_list)
    answer=max(answer_list)
    return answer

수정한 코드

point

• 문자열끼리 비교했다.
  • ASCII문자열로 비교가 되어서 앞에서부터 큰 수로 정렬이 가능하다.
  • map(str, {리스트})를 통해 형변환
• sorted로 정렬해줄 때, key값에 lambda 함수를 이용해서 세 자리의 값을 모두 비교해주어서 정렬했다.
  • 내림차순으로 정렬하기 때문에 reverse=True를 해준다.
• "".join(array)를 이용해서 문자열을 합쳐주었다.

# permutation 모든 경우의 수를 구하려고 하니 시간 초과 오류가 났다.
# 다른 방식으로 접근하는 것이 필요하다.

# 문자열을 내림차순으로 정렬한 다음, join 해주는 방식이다!
# 주의 : 처음에는 문자열로 비교할 것 !!(가장 큰 자릿수부터 비교 가능)


def solution(numbers):
    # 정수 type을 문자열 type으로 변경해주기 (map을 통한 형변환!)
    arr = list(map(str, numbers))

    # 문자열 크기대로 sorting하기
    # lambda : 1000이하의 정수이므로, x를 세 번 곱해주어 비교한다.
    array=sorted(arr, key=lambda x:x*3, reverse=True)

    # join으로 각각의 문자열들을 빈틈없이 붙여주기
    # int로 바꾸어주고, 다시 str으로 바꿔주기
    return str(int("".join(array)))

결과