프로그래머스 Lv2 가장 큰 수

문제

링크

풀이

내가 푼 풀이 (시간초과)

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))
    numbers.sort(reverse=True)
    i = 0
    while i != len(numbers) -1 : 
        a = numbers[i]
        b = numbers[i+1]
        if a + b < b + a :
            numbers[i], numbers[i+1] = b, a
            if i > 0  :
                i = 0
                continue
        i += 1
    return '0' if numbers[0] == '0' else ''.join(numbers)

먼저 숫자로 된 배열을 문자로 다 바꿔준다.
그리고 역순으로 정렬을 해줬다.
i번째 수와 i+1번째 수를 서로 붙여서 어떤 수를 앞에 두었을 때가 큰지 비교한다.
만약 i+1번째 수를 앞으로 붙였을 때가 크다면 i번째와 i+1번째수를 바꾼다.
이때 i가 0 이상이라면 처음부터 다시 비교하도록 했다.
왜냐하면 뒤에 있는 수를 앞으로 가져와야 수가 더 커지는 경우도 있기 때문이다.
하지만..역시나 시간초과였다.
도대체 이 문제를 어떻게 풀어야 하는지 머리가 돌아가지 않았다ㅠㅠ

참고한 풀이 1

def solution(numbers):
    numbers = list(map(str, numbers))
    temp = []
    answer = ''
    for i, value in enumerate(numbers) :
        while len(numbers[i]) < 4 :
            numbers[i] += value[:4-len(value)]
        temp.append([value, numbers[i]])
    temp.sort(key=lambda x : x[1], reverse=True)
    for t in temp :
        answer += t[0]
    return answer if answer[0] != '0' else '0'

결국 다른 분들의 코드를 참고해서 풀었다.

예를 들어 numbers가 [3, 30, 34, 5, 9] 이라고 하자.
numbers를 문자로 변경시키고 내림차순 정렬을 하면 ['9', '5', '34', '30', '3'] 순서로 출력된다.
왜냐하면 우선 순위가 맨 앞 숫자가 클 때, 그리고 자릿수가 많을 때 이기 때문이다.
['9', '5', '34', '3', '30'] 으로 정렬되어야 하는데 어떻게 하면 될까?

답은 반복이다.
조건에서 numbers의 원소는 0 이상 1,000 이하입니다. 라고 했으므로 반복을 통해 모든 원소를 4자리로 바꿔주면 된다.
그럼 numbers가 ['3333', '3030', '3434', '5555', '9999']가 된다.
numbers를 내림차순으로 정렬하면 ['9999', '5555', '3434', '3333', '3030']이 되므로 우리가 원하는 순서로 정렬된다.
나는 이전 수와 네자리로 변환한 수 둘 다 저장하기 위해 배열을 이용했다.
temp.sort(key=lambda x : x[1], reverse=True)로 정렬하고 0번째만 뽑아내면 정답을 구할 수 있다.

왜 반복을 해야하는지 문제를 풀어보니 이해는 가는데 정확하게는 잘 모르겠다.

-> 다른 분들의 코드를 살펴보면서 댓글을 보던 중 위의 의문을 조금 풀 수 있는 댓글을 발견했다.

숫자를 반복시키는 이유는 앞에서부터 같은 숫자패턴이 존재하는 숫자들의 비교를 위해서입니다.
기존 숫자를 반복시키게 되면 그 숫자가 앞에 왔을 때 만들 수 있는 최대 숫자를 만들 수 있습니다. (완전한 숫자는 아니구요. 비교가 가능한 범위까지 만들 수있어요)

참고한 풀이 2

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

같은 방법이지만 더욱 더 간단한 풀이로 풀 수 있다고 한다.
동일하게 배열을 문자열 리스트로 바꿔주고, 원소를 3번 반복한 것들로 비교한 후 정렬했다.

테스트로 코드를 돌려보니 답은 동일했다!

test = ['30', '3', '34', '5', '9']

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

test = ['303030', '333', '343434', '555', '999']

test.sort(key=lambda x: x, reverse=True)
print(test)

파이썬에서 문자열을 sort할 때 인덱스 하나씩 비교하면서 숫자, 문자 순서가 우위일 경우로 정렬한다는 사실을 알 수 있었다.

파이썬으로 문제를 풀고 자바스크립트로 다시 풀었다.

function solution(numbers) {
    numbers = numbers.map((num) => num + "");
    numbers = numbers.sort((a, b) => (b+a)-(a+b));
    return numbers[0] === '0' ? '0' : numbers.join('');
}

처음에는 파이썬과 동일하게 문자로 된 배열로 만들어준다.
그 다음 a+b, b+a 중 어떤 게 큰지 비교하면서 정렬하는데, 이를 구현하기 전에 sort가 어떻게 동작하는지 먼저 이해하고 진행하도록 하자.

sort 메서드

비교 함수는 양수나 음수 또는 0을 반환해야 한다.

• 비교 함수의 반환값

  • 0보다 작을 경우 : 첫 번째 인수를 우선하여 정렬
  • 0일 경우 : 정렬하지 않음
  • 0보다 클 경우 : 두 번째 인수를 우선하여 정렬

• sort((a, b) => a - b)

  • a - b < 0 이면 a를 우선으로 정렬한다.
  • a값이 b값보다 작으니까 a를 앞으로 보내므로 오름차순

• sort((a, b) => b - a)

  • b - a < 0 이면 b를 우선으로 정렬한다.
  • b값이 a값보다 작으니까 a를 뒤로 보내므로 내림차순
    
    

numbers = numbers.sort((a, b) => (b+a)-(a+b));

그렇다면 문제에서 작성한 위 코드는 어떻게 돌아가는지 확인해보자.

(b+a) - (a+b)로 두 문자를 비교한다.
위 식이 0보다 작다는 말은 b - a를 했을 때 0보다 작다는 말과 같으므로 a를 뒤로 보내 내림차순으로 정렬해줄 수 있다.
이 정렬 방식을 이용해서 문제를 풀면 답을 구할 수 있다.