프로그래머스 코딩테스트 고득점 Kit : 정렬 - (프로그래머스 42746번 : 가장 큰 수)

해당 문제는 프로그래머스에서 제공된 문제입니다.

오랜만의 문제 리뷰인 것 같다. 오늘은 고득점 kit 정렬 part에서 좀 까다로웠던 문제에 대해 다뤄보겠다.

 

[문제 설명]

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

먼저, 이 문제가 어떤 것을 요구하는지 어떤 방식으로 접근해야 되는지 살펴보자. 문제는 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하기를 요구하고 있다. 그렇다면 이를 어떻게 접근해야 될까? 이부분은 직접 숫자를 비교해가면서 방식을 구해야 된다고 생각한다. 예를 들면 1112와 11 중 누가 먼저 와서 이어져야 큰 수가 될 수 있을까? 1112이다. 결국, 앞자리만 비교한다고 되는 것이 아닌 앞자리와 뒷자리까지 긴 수에 맞춰서 비교해줘야 해당 문제를 풀 수 있는 것이다. 그럼 이제 코드를 통해 확인하자.

---

[문제 풀이]

def solution(numbers):
    answer = ''
    numbers = list(map(str, numbers))  # 숫자를 복사하기 위해 str로 변경
    max_len = sorted(map(len, numbers))[-1]  # 가장 큰 수의 길이를 확인
    compares = []  # 수를 복사하고 인덱스와 함께 저장하기 위한 리스트
    for i in range(len(numbers)):
        num = str(numbers[i]) * 4  # 해당 숫자들을 복제함
        new_num = [i, int(num[:max_len])]  # 복제한 숫자의 길이를 max_len으로 맞추고
        compares.append(new_num)  # 인덱스와 함께 저장
    result = sorted(compares, key=lambda x: x[1], reverse=True)  # 복제한 숫자들 크기 비교

    for idx, _ in result:  # 정렬된 리스트의 인덱스값 가져옴
        answer += numbers[idx]  # 해당 인덱스에 맞는 숫자를 차례대로 붙여줌

    if answer[0] == '0':  # 0일 경우 '0000' 이런식으로 표현되므로
        return '0'  # '0'으로만 반환
    return answer  # 결과 반환

결국 가장 큰 길이를 가지고 있는 수에 맞게 각각의 수를 복사하여 비교시켜야 한다. 그 후 복원을 위해 기존의 인덱스값을 저장해서 정렬해 준다음, 해당 인덱스 값을 통해 원하는 수를 만들어 낸다. 결론적으로 이 문제의 핵심은 리스트 안의 각각의 수들을 어떻게 비교 하냐 였다.

---

[잘못된 풀이]

처음에 나는 이 문제를 itertools의 permutation모듈을 사용하여 풀고자 했다. 그 결과 테스트의 모든 문제가 시간 초과가 나왔다. 접근 자체는 사실 일반적으로 생각할 수 있는 가능한 모든 경우의 수들 중 가장 큰 값을 반환하는 정석적인 방법이다. 하지만 이는 말 그대로 모든 경우의 수를 고려해야 하기 때문에 효율성을 따지는 문제에선 최악의 풀이가 된다. 기본적으로 비교할 수들이 N개에서 nPn으로 늘어나기 때문이다. 

---

[다른 사람의 풀이]

def solution(numbers):
    numbers = list(map(str, numbers)) # 문자열로써 비교하기 위해
    # 가장 긴 수의 길이가 최대 3이므로 (1000보다 클 수 없음) 비교를 위해 해당 수를 3번 복사해주고 문자열로써 비교하여 정렬
    numbers.sort(key=lambda x: x*3, reverse=True) 
    return str(int(''.join(numbers))) #정렬 결과를 반환

굉장히 깔끔하며 직관적인 코드이다. 내 코드와의 차이점을 말하자면 기본적인 접근 방식은 같으나 이 코드는 애초에 복사를 하고 해당 수를 자르지 않았고 또한 기존의 인덱스 값을 기억하지 않고서 lambda를 통해서 변형하고 비교하며 기존의 값들 또한 보존했다. 아주 훌륭한 코드라고 생각이 든다..

---

[마무리]

해당 문제는 level2라고 되어있지만 체감 상 level2.5정도는 되는 것 같다. 접근방식을 생각해내기가 쉽지 않은 문제였고 맞더라도 시간 초과로 인해 처음부터 다시 풀어야 하는 상황이 있었기에 좀 까다로웠다고 생각한다.