알고리즘 유형 : 정렬
풀이 참고 없이 스스로 풀었나요? : X
https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3
SOLVE 1
아스키 코드 기준으로 정렬하기 위해 자릿수를 세자리 수 이상으로 통일해주는 풀이
def solution(numbers):
answer = ''
numbers = list(map(str, numbers))
# 세자리 수 이상으로 자릿수를 맞추어 아스키 코드에 따라 정렬
# 네번째 자릿수부터의 수로 인한 정렬의 변화는 의미없음. 네번째 자릿수가 정렬에 영향을 미친다는 것은 세번째 자릿수까지의 수가 서로 같다는 뜻인데, 이 때는 실제로는 둘 다 같은 수 취급이므로 어떻게 정렬되든 상관없기 때문
numbers.sort(key = lambda x: x*3, reverse = True)
# 00, 000 같은 경우를 해결하기 위해 형변환
answer = str(int("".join(numbers)))
return answerSOLVE 2
여러 인자를 받는 함수를 key로 사용하여 정렬하는 풀이
from functools import cmp_to_key
def solution(numbers):
answer = ''
def compare(a, b):
a = str(a)
b = str(b)
# 그리디 개념 적용
s1 = int(a + b)
s2 = int(b + a)
if s1 < s2:
return 1
elif s1 > s2:
return -1
else:
return 0
numbers.sort(key=cmp_to_key(compare))
# 00, 000 같은 경우를 고려한 형변환
answer = str(int("".join(map(str, numbers))))
return answerSOLVE 1) 풀이 요약 (아스키 코드 기준으로 정렬하기 위해 자릿수를 세자리 수 이상으로 통일해주는 풀이)
- 숫자형 문자열을 아스키 코드 순으로 정렬을 할 것이므로 우선 numbers의 원소들을 str로 타입 캐스팅해준다.
-
아스키 코드 기준으로 정렬함은 곧 사전 순으로 정렬함과 같다.
최대한 큰 수를 만들기 위해선 가장 왼쪽 자릿수에 최대한 큰 숫자가 오도록 해야한다.
그리고 이는 곧 사전 역순으로 정렬하는 것과 같다.
- 그런데 역순으로 정렬 후 제출하면 오답 처리 된다. 뭔가 예외 케이스가 있는 것이다. 경우의 수를 차근차근 따져보자.
-
우선 자릿수가 같은 두 수를 생각해보자. 예를 들어 9와 4가 있다면 단순히 사전 역순 정렬하면 된다.
97 95, 48 22와 같은 경우도 사전 역순 정렬해주면 된다.
그럼 이제 자릿수가 다른 경우를 생각해보자.
예를 들어 23과 948은 사전 역순 정렬 그대로 해주면 된다.
87, 873같은 경우는 사전 역순으로 정렬하면 873, 87이 된다. 그런데 문제에서 구하고자 하는 답은 87873으로, 87이 앞에 와야한다. 이와 같은 경우를 고려하고자, 문자열에 *3을 하여 모든 숫자를 세자리 이상의 수로 바꿔준 후 사전 역순으로 정렬해준다.
87과 873에 대하여, 앞의 83은 둘다 같다. 그래서, 무엇이 앞에 오느냐에 따라 세번째 숫자가 3이 되거나 8이 된다.
일반화해보자. 즉, 자릿수가 다른 두 수에 대하여, 자릿수가 더 적은 숫자의 자릿수만큼의 숫자가 서로 같다면, 그 이후의 자릿수에 따라 순서가 결정되기 때문에(=두 수의 앞뒤 배치에 따라), 자릿수를 늘릴 때 0을 더 붙이거나 마지막 수를 연장해서 붙이거나 하지 않고 자신을 *3해서 덧붙여준다.
SOLVE 2 풀이 요약 (여러 인자를 받는 함수를 key로 사용하여 정렬하는 풀이)
- 이 풀이는 다인자 함수를 key로 하는 정렬과, 그리디 개념을 활용한 풀이이다.
-
임의의 두 수 a, b에 대해 정렬 순서 정보를 리턴하는 함수 compare를 작성한다.
그리디 개념을 적용한다.
a가 앞이고 b가 뒤일 때에 만들어지는 수 s1과 a가 뒤이고 b가 앞일 때에 만들어지는 수 s2에 대해, s1이 s2보다 크면 a가 앞인 것이고, s1이 s2보다 작으면 b가 앞인 것이고, 같으면 그 순서를 그대로 유지하도록 정보를 리턴해준다.그리고 이것을 sort의 key값으로 활용하기 위해, functools 모듈의 cmp_to_key 함수를 활용한다.
배운 점, 어려웠던 점
-
정렬 key로 커스텀 다인자 함수를 넣는 방법을 배웠다.
-
숫자 형태의 문자열을 정렬 시 아스키 코드, 즉 사전 순으로 정렬됨을 배웠다.
