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

2822 단어 algorithmalgorithm


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

풀이

처음에 permutations를 이용해서 순열을 모두 구하고 가장 큰 값을 뽑아냈더니
답은 맞지만 시간초과가 떴다.
그래서 정렬 문제구나 생각하고
문자열로 정렬을 했더니 [3, 30, 34, 5, 9] 예제에서
9 5 34 30 3 이 되는게 아닌가
어떻게 할까 고민하다가 결국 찾아본 결과
각 문자열을 스스로 몇번씩 곱해주면 해결된다는 신박한 방법을 알아냈다
각 문자를 5번씩 곱해주면
99999
55555
3434343434
3030303030
33333
이 되고
이걸 토대로 문자열 정렬을 역순으로 하면
9 5 34 3 30
이 된다.

def solution(numbers):
    arr = sorted(list(map(str, numbers)), key=lambda x: x*5, reverse=True)
    # ''.join(arr) 원래 여기 까지만 해주면 되나 [0,0,0,0] 들어올시를 대비해
    answer = str(int(''.join(arr)))
    return answer

쉬운 문제였는데 시간에 쫓기면서 하니 잘 안 풀린다.. ㅠ

좋은 웹페이지 즐겨찾기