프로그래머스 정렬 문제(2) (작성중)

내 풀이 아이디어 회고)

정렬 문제라고 하길래 내가 알고 있는 정렬 알고리즘 지식이 하나 이상 들어가는 문제를 낼 줄 알았는데, 전혀 아니었다. 정렬 문제라고 해서 반드시 내가 알고있는 정렬 알고리즘 범위 내에서 나오는 것도 아닌가 보더라.

느낌상, 뭔가 특정한 아이디어 딱 하나로 간단하게 푸는 문제인 것 같았는데

난 뭐 배경지식도 달리고 문제해결력도 아직 달려서 간단한 풀이로는 백프로 못풀 것 같았다

그래서 풀이를 볼까말까... 하다가 그냥 아는 지식만으로 최소한의 내 풀이 아이디어 전개라도 해보자고 생각했다. 생각하는 것에 의의가 있는게 알고리즘이므로.

 

원래 내가 문제풀 때 메모장 켜놓고 다음과 같은 방식으로 생각을 전개하므로, 전문을 복붙한다.

---

숫자 원소 꺼냄->스트링으로 만든 뒤, 스트링을 split하여 한 자리 한 자리 리스트로 반환함->이를 새로운 리스트에 추가하여 반환

첫번째 원소를 기준으로 정렬함 - 다만 리스트 안에 원소가 한개만 있어도 가능할지… 정렬할 때 개수가 중요한건 아닐지.

그러고 나면 앞자리가 같은 것끼리 정렬을 하면 되는데

이건 itemgetter에서 두번째 원소로 해결이 가능할까…

아 안되는게 원소가 한개만 있는 것끼린 안됨…

그럼 이 부분만…어떻게

 

확실한건 한자리 더 없는 것보단 있는게 앞에 나올 때 더 큰 수가 되고

이제 3,2,1자리 다 있을 땐 어떻게 할지…

이게 다른 수의 두번째 자리수가 첫번째 자리수보다 크냐 작으냐 이걸로 나뉘는군…

근데 이제 세자리수 섞여있으면…

3816 342 301 39 3 37

이걸 두자리수 기준 정렬하면

39 3816 37 342 3 301

393816

/.. 확실하다. 두번째 자리수 기준으로 정렬하면 되고, 한자리 수 인 3에 해당하는게 그 ..

Sort, sorted, reverse 할 때 기준으로 삼는 기능 있잖아 그걸로 하면 됨

 

34 334 3 30

아… 이 예를 따져보니까 또 단순한 문제가 아님을 알게됨…

두자리수도 같으면 세자리까지 가야하고…

말인 즉 이 문제의 이 부분에서 삼중 for loop을 돌릴 순 없으니, 뭔가 재귀가 됐든 뭐가 됐든 알고리즘 지식을 발휘해야 할듯함.

"""가장 앞자리 수만 추출하면 된다는... 이것만 뽑아내서 이걸 기준으로 리스트 정렬할 수 있을까?"""
from operator import itemgetter

def solution(numbers):
    answer = ''
    source1 = []
    insertelem = []
    for num in numbers:
        elemarr = str(num).split()
        if len(elemarr)==1:
            insertelem.append(elemarr)
            continue
        source1.append(elemarr)
        #del elemarr
    source2 = sorted(source1, itemgetter(0,1))

    if len(insertelem) != 0:
        for i in insertelem:
            for j in source2:
                if j[0] < i[0]:
                    source2.insert(source2.index(j),i)
                    break
                elif j[0] == i[0]:
                    #여기부턴 2번째 원소들 크기 보고, 그 중 이 아이가 들어갈 자리를 찾으면 되는데...
                    if j[1] < i[0]:
                        source2.insert(source2.index(j),i)
                    else:
                        
    return answer

---

풀이1)

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

sort(key=~)  풀이 나도 생각했다! 분명 저런 함수 같은 것도 기능으로 넣어서 쓸 수 있다는 것도 기억해서 이 방법으로 해보려고 했었음 근데 그 전에 풀이를 봐버렸네... 나는 sorted로 썼는데, 거기선 key가 내 생각대로 작동하지 않더라. 나는 for ~ in ~ 문장 썼음 저번에 봤던 exercism 풀이에 착안해서. 그래서 람다를 쓰려 했는데, 어떻게 쓸지 잘 모르겠더라... 아마 그 부분이 이 문제에서의 풀이 포인트였을 것 같음.

 

여기서 이 지식을 알고 가면 좋겠다.

"key"
 매개 변수의 값은 단일 인자를 취하고 정렬 목적으로 사용할 키를 반환하는 함수여야 합니다. 키 함수가 각 입력 레코드에 대해 정확히 한 번 호출되기 때문에 이 기법은 빠릅니다.

무엇보다 key도 함수 취급한다!

출처: https://docs.python.org/ko/3/howto/sorting.html

 

그럼 왜 3을 곱한 값을 정렬의 기준으로 삼는가? 여기서 주의해야할 점은 숫자에다가 3을 곱하는게 아니고 문자열에 3을 곱한 것, 즉 같은 문자열을 3번 반복해서 붙여놓는걸 말한다는 것 주의.

 

 

풀이2)

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

여기서 cmp_to_key는 아래 링크 sort 부분에 나와있더라. 고전적인 문법인듯,..? 이 라이브러리 알아두면 도움되나...

https://docs.python.org/ko/3/library/stdtypes.html#list.sort