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

코딩테스트 연습 - 가장 큰 수

<풀이>

처음에 어떻게 풀어가야할지 너무 막막했다. 무엇을 기준으로 정렬을 수행해야 할지 몰랐기 때문이다.

우선 각 숫자의 앞자리 숫자부터 비교해나가야 하는 것은 알 수 있는데 테스트 케이스로 주어진 34, 30, 3의 경우에는 무슨 기준으로 정렬해야 할지 고민하다가 결국 타인의 도움을 빌리기로 했다.

 

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

윗 분 블로그에서 힌트를 얻었다.

요약하자면 주어진 숫자를 반복해서 만든 4자리 이상의 숫자들을 정렬하면 된다는 얘기다.

예시) 34 -> 3434, 33 -> 3030, 3 -> 3333

 

1. 삽입 정렬 알고리즘 적용

def solution(numbers):
    number_list = []
    for number in numbers:
        n = str(number)
        for i in range(4 - len(n)):
            n += n[i]
        number_list.append((n, str(number)))
            
    for j in range(1, len(number_list)):
        for i in range(j, 0, -1):
            if number_list[i][0] > number_list[i-1][0]:
                number_list[i-1], number_list[i] = number_list[i], number_list[i-1]
            else:
                break
    
    answer = ''
    for number in number_list:
        answer += number[1]
    return str(int(answer))

이 코드는 돌아가지 않는다. 위 아이디어로 구현하려면 O(n^2) 알고리즘으로는 택도 없이 시간초과가 나온다.

(마지막에 int로 바꿔주고 다시 str로 바꿔준 이유는 '0000'의 경우 '0'이 출력되어야 하기 때문이다.)

 

2. 내장 함수 sort() 활용

def solution(numbers):
    number_list = []
    for number in numbers:
        n = str(number)
        for i in range(4 - len(n)):
            n += n[i]
        number_list.append((n, str(number)))
                
    number_list.sort(reverse=True)
    
    answer = ''
    for number in number_list:
        answer += number[1]
    return str(int(answer))

그래서 sort() 함수를 활용하니 통과가 되기는 한다.

 

<다른 사람의 풀이>

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

다른 사람의 풀이를 봤는데...경이롭기까지 하다...

 

이 풀이에서 내장 함수 sort()를 활용하기는 했는데 정렬 알고리즘을 연습하기 위해 퀵 정렬 알고리즘을 직접 풀어보기로 했다.

 

3. 퀵 정렬 알고리즘 적용

def solution(numbers):
    number_list = []
    for number in numbers:
        n = str(number)
        for i in range(4 - len(n)):
            n += n[i]
        number_list.append((n, str(number)))
        
    def quick_sort(start, end):
        if start >= end:
            return
        pivot = start
        left = start + 1
        right = end
        
        while left <= right:
            while left <= end and number_list[left][0] >= number_list[pivot][0]:
                left += 1
            while right > start and number_list[right][0] <= number_list[pivot][0]:
                right -= 1
                
            if left > right:
                number_list[right], number_list[pivot] = number_list[pivot], number_list[right]
            else:
                number_list[right], number_list[left] = number_list[left], number_list[right]
            quick_sort(start, right -1)
            quick_sort(right+1, end)
                
    quick_sort(0, len(number_list) - 1)
    
    answer = ''
    for number in number_list:
        answer += number[1]
    return str(int(answer))

이런 식으로 퀵 정렬을 구현해봤지만 절반 정도의 테스트 케이스에서 런타임에러가 속출했다..ㅠㅠ

일단 방법을 찾아봤는데 실패..다음에 재시도하는걸로..