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

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 한다.

 

# 입출력 예

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

 

# 풀이

- 먼저 각 숫자들을 문자열로 바꾸고, permutations 함수를 이용하여 순서를 고려한 조합을 tmp 리스트로 받는다.- 각 조합에서 숫자들을 이어 붙인 뒤 lst 리스트에 저장해주고, 내림차순 정렬을 하여 제일 첫 번째 값을 출력하면 된다.

from itertools import permutations

def solution(numbers):
    lst = []
    numbers = list(map(str, numbers))
    tmp = list(permutations(numbers, len(numbers)))

    for t in tmp:
        num = ''.join(t)
        lst.append(num)
    lst.sort(reverse=True)
    return str(lst[0])

- 시간 초과 판정을 받아서 시간 복잡도를 고려한 코드 수정이 필요하다.

 

# 수정된 풀이

- 도저히 다른 방안이 생각나지 않아서 다른 사람들의 풀이를 보고 공부해보았다.

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

- 우선 이 문제는 itertools의 permutations를 이용하면 완전 탐색을 수행하게 되므로 시간 초과 판정을 받게 된다.

- 문제 해결의 키포인트는 숫자들을 ascii 숫자로 바꿔서 비교하는 것과 0이상 1,000이하라는 조건을 이용하는 것이다.

- 문제의 예시인 [6, 10, 2]를 numbers.sort(key=lambda x: x*3, reverse=True) 코드에 통과시켜보면, 

  [666, 101010, 222] -> [666, 222, 101010] -> [6, 2, 10] 처럼 된다.

- 그 이유는 문자열 비교연산의 경우에 첫번째 인덱스의 ascii 숫자를 비교하게되고, 이에 앞자리가 큰 순으로 6, 2, 1로 정렬이 되기 때문에 [6, 2, 10]으로 정렬이 된다고 한다.

 

# 고찰

- 시간 초과 판정을 해결하기 위해 현재의 지식으로 아무리 노력(퀵정렬과 같이 정렬의 방식을 바꾸는 노력)해봤지만

  역부족이었다.

- 아무래도 여러 문제를 통해 풀이 방식을 익히는 수 밖에 없을 것으로 판단된다.