프로그래머스 - 가장 큰 수(정렬)

문제 설명

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

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

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

제한 사항

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

입출력 예numbersreturn

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

---

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

 

나이 풀이(시간 초과)

#모든 순열을 구하고 그 중 가장 큰 값
import itertools


def solution(numbers):
    p = itertools.permutations(numbers, len(numbers))

    answer_list = []
    for i in p:
        answer = ''
        for j in i:
            answer += str(j)
        answer_list.append(answer)

    return max(answer_list)

1) 해당 조합 중 가장 큰 값을 반환하는 알고리즘인데, 시간 복잡도가 형편없는 것을 알았고 이렇게 접근하면 안될 것 같긴했지만 아래 풀이를 생각하지 못했었다.

 

정렬 풀이

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True) #x*3을 하면, 문자열 세번 반복하여 곱해짐 아스키 코드(숫자를 문자열로 바꾼 번호)는 각 자리 수마다 값을 비교할 수 있음.
    
    return str(int(answer.join(numbers)))  #모든 값이 0일 때, '000'이 아니라 '0'을 반환하기 위함

 

1) 리스트 안에 모든 수를 문자열로 바꿔준다.

 

2) 모든 수는 1000 이하 이므로 세자리로 모두 맞춰준 후 비교한다. 참고로 숫자가 문자열로 바뀐 다음에는 아스키 코드 기준으로 정렬이 된다. 따라서 숫자 전체의 크기가 아니라 문자로 보기에 첫번째 인덱스부터 비교를 한다.

ex) '666' > '6653'로 정렬 우선순위에 있다. 세번째 인덱스인 6과 5중 6이 더 큰 수이므로 

 

3) 모든 값이 0일 때는, '000'이 아니라 '0'을 반환해야하므로 값을 다시 정수를 만들어주고 문자로 반화해야한다!