[프로그래머스/Lv2] 가장 큰 수

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

프로그래머스

 

 

코드

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers = sorted(numbers, key=lambda x: x*3, reverse=True)

    return str(int(''.join(numbers)))

 

 

설명

풀다가 시간이 너무 걸려서 포기하고 다른 사람의 풀이를 봤다.

다른 언어들에서(자바, swift 등)는 numbers의 원소를 str으로 변환한뒤 첫번째 원소와 두번째 원소를 앞 뒤 순서를 바꿔가며 더해, 더 큰 수가 나오는 순서로 정렬하는 방법으로 문제를 푸는 경우가 많았다.

파이썬으로 동일하게 구현하려 하니 반례 케이스의 오류를 잡는데 시간이 너무 걸려서 결국 다른 풀이를 봤다.

 

간단하게 설명해서 우리는 [3, 30, 34]가 [34, 3, 30]으로 정렬되기를 바란다.

그런데 사전순으로 정렬하든 숫자의 크기로 정렬하든 우리가 원하는 답으로 나오지는 않는다.

만약 입력된 숫자들의 자릿수가 모두 동일하다면 어떨까

[3, 30, 34]가 [33, 30, 34]라면 사전순으로 정렬하면 [34, 33, 30], 33을 다시 3으로 바꾸면 [34, 3, 30]으로 우리가 원하는 답이 나온다.

즉, 숫자를 비교할 때 자릿수를 맞춰주고 사전순으로 정렬하게 하면 된다는 뜻이다.

 

문제에서 numbers의 원소는 1에서 1000이하의 자연수라고 했다.

네자릿수 수는 1000 하나밖에 없으니 모든 수를 최소 세자리수가 되도록 수정해준 뒤, 사전순으로 정렬하면

원하는 답을 찾을 수 있을 것이다.

 

파이썬에서는 문자열에 n을 곱하면 문자열이 n번 반복된다.

이 것을 통해 자릿수가 최소 세자리가 되도록 수정해줄 것이다.

 

문제의 예제를 통해 살펴본다.

[3, 30, 34, 5, 9]에서 각각의 문자열을 세번씩 곱하면

[333, 303030, 343434, 555, 999]가 된다.

여기서 사전순으로 정렬할 건데, 이해하기 쉽게 세자리수까지만 남도록 보자.

[333, 303, 343, 555, 999]

이 리스트를 사전순으로 정렬하면

[999, 555, 343, 333, 303]이 된다.

그리고 문자열을 곱하기 전으로 되돌리면

[9, 5, 34, 3, 30]으로 우리가 원하는 정답이 나오게 된다.

 

이 과정을 코드로 옮기면 된다.

 

numbers = list(map(str, numbers))

numbers의 원소들을 모두 str으로 형변환한다.

 

numbers = sorted(numbers, key=lambda x: x*3, reverse=True)

numbers의 원소를 정렬한다.

이 때 lambda함수로 입력되는 x를 3번 곱하여 그것을 기준으로 정렬하도록한다.

reverse=True 옵션으로 내림차순으로 정렬하도록 한다.

 

return str(int(''.join(numbers)))

정렬된 numbers를 ''을 구분자로 join한 뒤 int형변환하고 str형변환한 값을 반환한다.

int형변환 -> str형변환은 "00123" 같은 문자열을 "123"으로 변경시켜주기 위함이다.

---

참고1 : https://velog.io/@insutance/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Python-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%88%98

[프로그래머스][Python] 가장 큰 수

 

참고2 : https://huidea.tistory.com/4

[프로그래머스] 가장 큰 수 정렬문제 python (200713)

 

참고3(swift) : https://caution-dev.tistory.com/4

[알고리즘][Swift] #2. 가장 큰 수