FrontEnd
Javascript
Diary
ML
CS
Django
Algorithm
AWS
Co-Work
HTML
CSS
Python
React
ReactNative

#61 알고리즘 연습 - 가장 큰 수(Python)

가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • numbers의 길이는 1 이상 100,000 이하입니다.
  • numbers의 원소는 0 이상 1,000 이하입니다.
  • 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers return
[6, 10, 2] 6210
[3, 30, 34, 5, 9] 9534330

문제풀이 IDEA

이번에도 역시나 TEST CASE를 찾아서 생각의 빈틈을 메우는게 중요했던 문제인데, 위의 입출력에서만 주어진대로 코드를 짜면 예외 케이스가 너무나 많았다.

일단 문제를 해결해나가는 방향이 처음에는 9 8 7 이런식으로 숫자를 정렬해야하는 느낌은 있었는데, 이것을 어떤식으로 두자리, 세자리를 판별해 주는지가 문제였다. 그래서 생각을 해보니 3 과 34의 경우 34를 조합했을때가 더 큰 숫자가 되고, 예외적으로 30 은 3 하나보다 작은 숫자를 생성하게된다.

따라서 숫자를 정렬하기 보다 숫자를 문자로 취급해서 정렬을 해주고, 해당 순서에서 마지막 자리에 0이 올때는 예외로 취급을 해주는 코드를 짰으나 정확도에서도 처참했다.

그 이유는 어떤 분께서 올려주신 [2,20,200] 인 TEST CASE를 통과하지 못해서이다. 즉 그때서야 처음했던 사고자체에 허점이 많은것을 알게 되었는데 32도 3보다 작은 숫자를 만들 여지가 남아있다는 것이다.

그래서 생각을 처음부터 다시하기로 하고 일의자리, 십의자리, 백의자리 케이스를 나누어 몫과 나머지로 어떻게 안되나 생각도 해보다가 모두 4자리로 통일을 시키고, 남은 자리수는 다른 숫자와 비교할 수 있는 기준이 되는 숫자로 채워 주는 방법을 택했다. 예를 들면 34 랑 3을 비교하면 34를 쓰는게 이득인데 3444 , 3333이렇게 채워준다고 생각할수 있고. 한단계 더 나가서 20 이랑 200이랑 비교하면 20을 쓰는게 이득인데 이때는 2000, 2000을 해서는 비교가 불가능 하므로, 2020, 2000으로 비교를 하는게 기준이 더 명확한것 같다. 그래서 남은 자리수는 반복으로 채워줄 예정이다.

내 풀이 🌱

def solution(numbers):
    sort_list = [] #문자를 기준으로 정렬된 애들을 보관하기 위한 list이다.
    cnt = 0        #그리고 정렬된 list와 original list의 element들을 대응 시키기 위한 cnt이다.
    for i in numbers:
        sort_list.append(((str(i)*4)[:4], cnt)) #i가 일의 자리일때를 대비해 4번 반복하고, 4만큼 잘라서 정렬할 list에 차곡차곡 넣어준다. 그러면 cnt랑 tuple형태로 list에 차곡차곡 쌓이는데
        cnt += 1

    answer = "".join([str(numbers[i[1]]) for i in sorted(sort_list, reverse=True)])
    #위의 코드에서 들어가 있는 sort_list를 역순으로 정렬하게되면 tuple의 첫번째 index를 기준으로 정렬이 되고 해당 list를 돌면서 i를 가져오는데, 이때의 i는 tuple의 모양을 한다 (2020, 1)따라서 i의 1번인덱스인 original list에서의 자리수를 가져와서 number에서 찾아주는 코드이다.
    if not int(answer): #그리고 만약 0000일때를 대비해서 int를 썼을때 0이되면 false이므로 not을 붙여서
        return "0"      #0000일때는 0을 반환하자

    return answer

내 풀이(리팩토링) 🌱

def solution(numbers):
    sort_list = []
    for i in numbers:
        sort_list.append((str(i)*4)[:4])

    answer = "".join(sorted(sort_list, reverse=True))

    if not int(answer):
        return "0"

    return answer

문제를 풀고 되게 획기적인 생각이다고 생각했는데 역시 아직 멀었다. 가독성이나 한눈에 이해하기 어려운 코드를 짜버렸다.

어…? 그런데 밑에 코드를 보다 보니 왜 cnt를 써서 원 함수에서 뽑아와야한다고 생각했을까 sorted된 list를 바로 join하면 되었을 것 같은데 괜히 cnt를 넣어서 tuple도 쓰고 예전에 tuple을써서 푼 algorithm 코드가 인상깊어서 불필요한 부분을 추가한것 같다.

다른 풀이 🌳

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

나랑 같은 방법으로 풀어주었는데, 대신 map함수를 이용해서 number를 str과 대응시켜 numbers list를 string으로 덮어써주고 그 string list를 sort해주는 대신(immutable하지는 않다.) key값으로 각 원소를 3번씩 반복한 key값을 사용했다.(이는 1000이하이기때문에 1이 세번반복되어도 111은 1000보다 크다.(문자열에서))

그리고 역순으로 정렬된것을 int로 한번 갔다가 오면 0000이 0처리가 되므로 string으로 바로 다시 바꿔주면된다

다른 풀이2 🌳

다른풀이 2번은 functools.cmptokey 를 이용한 풀이였다. 그래서 해당 풀이법을 해석하기위해 cmptokey의 내부 동작을 이해하고 포스팅을 하려고 했으나, 찾아봐도 내부적으로 K class를 생성하여 instance 들끼리 비교하는 method를 실행시킨다고 나와있었다. 그리고 python 2.x version의 legacy code를 변환할때나 혹은 custom cmp를 만들때(이마저도 람다식을 이용하면 금방 할것 같긴하다) 쓴다고하는데 도무지 원론적인 동작원리가 이해가 가지않아서 나중에 다시금 더 똑똑해지면 돌아와야겠다.

>>> def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K(object):
        def __init__(self, obj, *args):
            print('obj created with ',obj)
            self.obj = obj
        def __lt__(self, other):
            print('comparing less than ',self.obj)
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            print('comparing greter than ',self.obj)
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            print('comparing equal to ',self.obj)
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            print('comparing less than equal ',self.obj)
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            print('comparing greater than equal',self.obj)
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            print('comparing not equal ',self.obj)
            return mycmp(self.obj, other.obj) != 0
    return K

>>> def mycmp(a, b):
    print("In Mycmp for", a, ' ', b)
    if a < b:
        return -1
    elif a > b:
        return 1
    return 0

>>> print(sorted([3,4,2,5],key=cmp_to_key(mycmp)))
obj created with  3
obj created with  4
obj created with  2
obj created with  5
comparing less than  4
In Mycmp for 4   3
comparing less than  2
In Mycmp for 2   4
comparing less than  2
In Mycmp for 2   4
comparing less than  2
In Mycmp for 2   3
comparing less than  5
In Mycmp for 5   3
comparing less than  5
In Mycmp for 5

위의 코드가 cmptokey를 설명한 코드인데… 나중에 다시 봐야겠다.

처음에는 재미로 풀기 시작한 Algorithm인데 풀면 풀수록 약간 이론적인 공부의 필요성을 느낀다. 그리고 주어진 입출력만으로는 생각의 헛점이 많아 TEST CASE를 생각하는 능력도 중요해지고 있는데, 이러한부분을 연습해두면 실 서비스를 개발함에 있어 방어코드도 보다 잘 작성할수 있는 능력이 배양될 것 같다는 생각이 들었다.