[프로그래머스] 정렬 2. 가장 큰 수

문제

출처: 프로그래머스

---

풀이

레벨 2라고 벌써 어렵다.;

처음에 생각했던 방법은 다음과 같다.

만약 [3, 31, 375, 37, 370, 8]의 numbers가 주어진다면 다음과 같이 각 자릿수를 분리하여 이중배열을 만든다.

3	3	3	3	3	8
	1	7	7	7
		5		0

그 후

1. 첫 번째 자릿수의 숫자를 비교하여 정렬

2. 만약 같은 숫자일 경우, 두 번째 자리 수 중 큰 순서로 정렬

3. 만약 같은 숫자이며 두 번째 자리 수가 없는 경우, 첫 번째와 같은 숫자로 취급하여 비교 후 정렬 ex) 3 -> 33

4. 세 번째 자리 수도 같은 방법으로 비교 후 정렬

 

위의 방법으로 풀면, 내가 생각한 예외는 대강 잡힐 것 같았다. (이마저도 틀릴수도)

다만 문제는 그 다음이었다.

각 과정이 너무 복잡했고, 시간과 공간 활용도 좋지 못할 듯 했다.

 

이 풀이를 의도한 것 같진 않아 다른 방법을 생각해 보았는데 잘 떠오르지 않아 다른사람의 풀이를 참고했다.

 

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

이렇게 짧게 끝날 풀이였다니,, 천재 너무 많다

중요한 발상은 문자열으로의 변환이었다. 왜 이 생각을 못했지

numbers = list(map(str, numbers))

숫자였던 numbers배열을 string형으로 변환해 다시 배열로 리턴한다.

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

list.sort()와 sorted()는 모두 비교하기 전에 각 리스트 요소에 대해 호출할 함수(또는 다른 콜러블)를 지정하는
key 매개 변수를 가지고 있습니다.

쉽게 말해 key를 기준으로 정렬한다. 여기서 lambda를 사용해 x*3을 해준 이유는 numbers의 원소는 0이상 1000이하라는 조건 때문이다.

위의 예시를 다시 사용하자면 31, 375, 8은 313131, 375375375, 888이 되고 아스키코드 기준으로 역순정렬(8, 375, 31)된다.

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

'구분자'.join(list) :리스트에 특정 구분자를 추가하여 문자열로 변환함

정렬된 숫자를 합치고 int형으로 변환 후 다시 str로 변환하여 리턴한다.

[0, 0, 0]이 주어졌을 때 000으로 반환하지 않도록 하기 위함이다. 이 과정을 생략하면 12번 케이스에서 통과하지 못한다.

---

시간, 공간 활용

내 코드는 아니지만 다음과 같다.

요새 느끼는 점이 있다면, 코딩테스트는 이미 자체적인 시간, 공간활용의 커트라인이 있으니 그 내에서라면 내장함수의 도움도 받고 더 간단한 풀이 방법을 택하는 편이 좋겠다는 것이다.

물론 시간복잡도를 줄이는 것은 바람직하나 실제 코테에서는 주어진 시간이 그리 넉넉하지 않을 거라 생각되기 때문이다. 면접에서 코테 문제 풀이과정을 물어보는지는 기회가 될 때 선배에게 물어보려 한다.

 

 

 

참고:

hocheon.tistory.com/48

docs.python.org/ko/3/howto/sorting.html

zetawiki.com/wiki/%ED%8C%8C%EC%9D%B4%EC%8D%AC_join()