프로그래머스 가장 큰 수(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

처음 이 문제를 접했을 때는 "permutations 쓰면 금방 해결할 문제 아닌가?" 생각하면서 만만히 봤습니다. permutations 사용해서 풀어본 결과 시간 초과가 떴습니다..... 아마 최대 10만 개 요소들에 대한 순열을 생성하는 과정에서 시간이 많이 소요되지 않았을까 생각이 듭니다.(확실 X)

permutations를 너무 믿은 나머지 다른 풀이법이 생각나지 않아 결국 이번에도 다른 분의 코드를 보며 배웠습니다.

 

다른 사람의 풀이

https://jokerldg.github.io/algorithm/2021/05/06/most-big-number.html

프로그래머스 가장 큰 수 (python 파이썬) - Tech

이 분은 순열을 사용하지 않고 문자열의 정렬만 사용해서 풀어내셨습니다. 이는 문자열의 정렬은 ASCII 값으로 바뀌어서 정렬된다는 아이디어에서 출발합니다.

예를 들어 ["6", "0", "2"]를 정렬한다고 합시다. 이 요소들을 ord()를 이용해 ASCII 값으로 바꾸면 각각 54, 48, 50입니다. 아스키 값 기준으로 이를 정렬하면 ["0", "2", "6"]이 되고 이는 숫자처럼 생각했을 때와 똑같이 정렬됨을 확인할 수 있습니다.

하지만 이 문제에서는 각 요소가 최대 1000까지 될 수 있습니다. 이 때 각 요소들을 비교하는 방법을 생각해야 했는데 여기서는 각 요소를 3번씩 반복해서 비교할 수 있게 했습니다.

예를 들어 ["6", "10", "2"]를 정렬한다고 합시다. 각 요소들을 세 번씩 반복한 결과는 ["666", "101010", "222"]입니다.

여기서 맨 앞의 자리부터 값을 비교하게 되니 결국 "6", "1", "2" 사이의 비교가 됩니다. 비교의 결과로 정렬하면 ["101010", "222", "666"]이 되고 실제 결과는 ["10", "2", "6"]이 됩니다. 이를 역순으로 정렬하면 ["6", "2", "10"]이 되고 이를 붙여서 만든 수가 가장 큰 수가 됩니다. 이 경우는 세 번 반복시키지 않고 그냥 역순 정렬만 시켜도 같은 결과가 나옵니다. 세 번 반복시키는 행동은 다음 예시에서 그 진가가 나옵니다.

이번에는 ["3", "30", "34", "5", "9"]를 역순으로 정렬한다고 합시다. 그냥 정렬시키면 ["9", "5", "34", "30", "3"]이 되어 가장 큰 수는 9534303이 됩니다. 하지만 이는 실제 큰 수인 9534330보다 작습니다. 그러니 이번에도 각 요소를 세 번 반복시켜봅시다. ["333", "303030", "343434", "555", "999"]가 되고 첫 번째 자리를 기준으로 우선 역순 정렬하면 ["999", "555", "333", "303030", "343434"]로 될 것입니다. "333" ~ "343434"는 맨 앞이 "3"으로 같습니다. 이때 두 번째 자리를 기준으로 이들을 다시 정렬시키면 ["999", "555", "343434", "333", "303030"]이 되면서 정렬이 끝납니다. 이는 실제로 ["9", "5", "34", "3", "30"]이 되고 이를 이어붙이면 9534330으로 가장 큰 수가 됩니다.

왜 이렇게 하는가?

지금까지 설명을 보고 이해가 안 될수도 있습니다. 저도 그랬으니까요... 그렇기 때문에 계속 설명을 붙여 나가겠습니다.

세 번 반복하는 이유가 아직도 와닿지 않을 수도 있습니다. ["3", "30"]의 경우를 봅시다. 이는 ["3", "51"]이나 ["3", "17"] 같은 경우보다 생각해야 하는 경우입니다. ["3", "51"]이나 ["3", "17"]은 앞 자리만 비교해서 큰 순서대로 붙이면 바로 최댓값을 얻을 수 있지만 ["3", "30"]의 경우는 앞 자리 숫자가 같은 상황입니다. 이때 그냥 큰 숫자 순서대로 이어 붙이면 303을 얻습니다. 이는 최댓값이 아닙니다. 330이 최댓값입니다. 하지만 ["3", "34"] 같은 경우면 큰 순서대로 이어 붙이는 게 최댓값입니다.

["3", "30"]의 경우, "30"의 "0"이 "3"보다 작습니다. 이와 같이 다음 자릿수가 3보다 작으면 "3"의 앞에 붙는 것보다 뒤에 붙을 때 더 큰 수를 만들 수 있습니다. ["3", "34"] 같은 경우면 "34"의 "4"가 "3"보다 크기 때문에 "3"의 앞에 붙어야 큰 수를 만들 수 있습니다.

이를 쉽게 비교하기 위해 요소들을 각각 두 번 반복해봅시다. ["33", "3030"] 사이의 비교, ["33", "3434"] 사이의 비교가 됩니다. 이들을 가장 앞의 자릿수부터 비교하면 더 직관적으로 비교해서 정렬할 수 있게 됩니다. ["33", "3030"]은 "3"과 "0" 사이의 비교, ["33", "3434"]은 "3"과 "4"의 비교가 되기 때문입니다.

프로그래머스에서는 요소의 최댓값이 1000이기 때문에 그래서 요소들을 세 번 반복시켜 자릿수를 늘리는 것입니다.

 

마지막에 이 결과들을 정수형으로 바꾸고 다시 문자열로 바꾸는데 이는 ["0", "0", "0"]이 입력으로 들어오는 경우 가장 큰 수는 "000"이기 때문에 "0"을 반환하기 위해서 정수형으로 한 번 바꾸고 다시 문자열로 변환합니다.

지금까지의 설명을 코드로 하면 아래의 코드가 됩니다.

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

프로그래머스 채점 서버에서 이 분의 코드를 돌려본 결과, 최대 1271.26 ms, 27MB의 자원을 사용했습니다.

 

이번 문제는 자료 구조보다는 아이디어가 중요한 문제였던 것 같습니다.