[Level 2] 정렬. 가장 큰 수

 문제 

https://programmers.co.kr/learn/courses/30/lessons/42746?language=python3 

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

 사용 언어 

Python3

 풀이 과정 

처음에 풀었던 답안은 다음과 같다. 이것도 처음에 if문으로 case를 엄청 나누다가 이게 아닌것 같아 다 엎고 질문하기에서 힌트를 얻어 작성한 코드인데... 아래와 같이 틀린 케이스가 절반이나 돼서 ㅋㅋㅋㅋㅋㅋ 한숨 쉬고 틀린 예제를 찾았다.

def solution(numbers):
    answer = ''
    numbers = map(str, numbers)
    numbers = [(num, len(num)) for num in numbers]
    new_list = []
    zero = 0
    thousand = 0
    for each in numbers:
        length = each[1]
        if length == 1: # 한 자리수이면
            if each[0] == '0': # 0이면
                zero += 1 # 0의 개수
                continue
            new_list.append((each[0]*3, length)) # 세 번 이어붙인 값
        elif length == 2: # 두 자리수이면
            new_list.append((each[0] + each[0][0], length)) # 두 자리와 둘 중 앞자리 이어붙인 값
        elif length == 3: # 세 자리수이면
            new_list.append((each[0], length)) # 그대로
        else: # 네 자리수이면
            thousand += 1 # 천의 개수

    new_list.sort(key = lambda x : (x[0][0], x[0][1], x[0][2], x[1]), reverse = True)

    for each, length in new_list:
        answer += each[:length]
    answer = answer + '1000' * thousand + '0' * zero

    if int(answer) == 0:
        return '0'

    return answer

나는 [87, 878]의 케이스에서 "87887"이 나오도록 하기 위해 sort lambda 마지막에 총 길이를 내림차순 정렬하라고 추가해주었는데 이러면 [89, 898]의 경우 정답인 "89898"이 아닌 "89889"가 나온다. 이 문제를 해결하기 위해 저 자리에 if문을 넣을지 대소 비교를 넣을지 오래 고민했는데 결국 가독성은 개나 줘버린 코드로 성공했다. 알고보면 삼항연산자와 마이너스를 이용해 정렬 기준을 뒤집어준 것. 최종 수정해서 제출한 답안의 결과는 아래와 같다.

아래 다른 사람들 코드와 비교해보니 오... 시간복잡도는 좋은듯하다.

 제출 답안 

def solution(numbers):
    answer = ''
    numbers = map(str, numbers)
    numbers = [(num, len(num)) for num in numbers]
    new_list = []
    zero = 0
    thousand = 0
    for each in numbers:
        length = each[1]
        if length == 1: # 한 자리수이면
            if each[0] == '0': # 0이면
                zero += 1 # 0의 개수
                continue
            new_list.append((each[0]*3, length)) # 세 번 이어붙인 값
        elif length == 2: # 두 자리수이면
            new_list.append((each[0] + each[0][0], length)) # 두 자리와 둘 중 앞자리 이어붙인 값
        elif length == 3: # 세 자리수이면
            new_list.append((each[0], length)) # 그대로
        else: # 네 자리수이면
            thousand += 1 # 천의 개수

    new_list.sort(key = lambda x : (x[0][0], x[0][1], x[0][2], x[1] if x[0][0] >= x[0][1] else -x[1]), reverse = True)

    for each, length in new_list:
        answer += each[:length]
    answer = answer + '1000' * thousand + '0' * zero

    if int(answer) == 0:
        return '0'

    return answer

 공부한 내용 

lambda 함수 이해하기

'익명 함수'라고도 불리는 lambda 함수는 함수를 선언하고 생성하지 않아도 간단히 쓸 수 있어 일회용으로 쓸 함수를 만들 때 특히 유용하다. 결과값을 저장할 변수를 왼쪽에 선언하고 오른쪽에 lambda x : x*3과 같은 형태로 함수를 선언한다. 따라서 함수 선언 길이를 훨씬 단축할 수 있다.

lambda_x = lambda x: x * 3
print(lambda_x(2)) # 6

다음과 같이 인자를 여러개 받을 수도 있다.

lambda_xy = lambda x, y: x + y
print(lambda_xy(4, 4)) # 8

lambda함수는 다른 메소드나 조건과 함께 쓰면 더 유용할 때가 많다.

 

lambda 함수와 if문

lambda 함수 안에 여러 조건들을 설정할 수 있다. 주의할 점은 보통의 if문과 다르게 출력 값이 먼저 나온다는 점이다.

score = lambda x: "A등급" if x >= 80 else "B등급" print(score(50)) # B등급

다중 조건도 설정할 수 있는데 ()로 구분하여 가독성을 높인다.

score = lambda x: "A등급" if x >= 80 else ("B등급" if x >= 70 else "C등급")
print(score(50)) # C등급

여기서 주의할 점은 기존의 if문과 다르게 사용할 때 else문을 꼭 써줘야 한다는 것이고 else if나 elif같은 건 없음에 유의한다.

 

lambda 함수와 map()

인자가 여러 개라면 보통 list를 만들어서 넣는다. lambda 함수는 이럴 때 map 함수를 사용한다.

다만 map 함수는 아래와 같이 map 객체로 반환되기 때문에 리스트로 사용하고 싶다면 list() 메소드를 추가로 사용해줘야 한다.

a = [1, 2, 3]
lambda_map = map(lambda y: y ** 2, a)
print(lambda_map) # <map object at 0x00000241180052B0
print(list(lambda_map) # [1, 4, 9]

 

lambda 함수와 sort()

sort, sorted 모두 key, reverse 매개변수를 가지고 있다.

1. reverse

bool값을 넣는다. 기본값은 reverse=False(오름차순)이다.

reverse=True를 매개변수로 입력하면 내림차순으로 정렬할 수 있다.

>>> num_list = [15, 22, 8, 79, 10]
>>> num_list.sort(reverse=True)
>>> print(num_list)
[79, 22, 15, 10, 8]

>>> print(sorted(['좋은하루','good_morning','굿모닝','niceday'], reverse=True))
['좋은하루', '굿모닝', 'niceday', 'good_morning']

2. key

정렬을 목적으로 하는 함수를 값으로 넣는다. lambda를 이용할 수 있다.

key 값을 기준으로 정렬되고 기본값은 오름차순이다. 

>>> str_list = ['좋은하루','good_morning','굿모닝','niceday']
>>> print(sorted(str_list, key=len))  # 함수
['굿모닝', '좋은하루', 'niceday', 'good_morning']

>>> print(sorted(str_list, key=lambda x : x[1]))  # 람다
['niceday', 'good_morning', '굿모닝', '좋은하루']

여러 개의 요소를 가진 경우, 튜플로도 사용할 수 있다.

>>> tuple_list = [('좋은하루', 0),
    	          ('niceday', 1), 
    	          ('좋은하루', 5), 
    	          ('good_morning', 3), 
    	          ('niceday',5)]
                  
>>> tuple_list.sort(key=lambda x : (x[0], x[1]))  # '-'부호를 이용해서 역순으로 가능
>>> print(tuple_list)
[('good_morning', 3), ('niceday', 1), ('niceday', 5), ('좋은하루', 0), ('좋은하루', 5)]

 

출처: https://wpaud16.tistory.com/55 | https://ooyoung.tistory.com/59

 다른 사람 답안 

와 진짜 이렇게 간결할수가 있나. 역시 현타오는 답안. Level 2가 왜이렇게 어렵나 했는데 어렵게 푸니까 어려운거였다...

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

출처: 프로그래머스   

 

그래도!!! 이렇게 간결한 코드는 가장 시간복잡도가 좋지 않다는 것. 가독성과 맞바꾼 효율이라고 할 수 있다.

하지만 나는 알면서도 안짜는 것이 아니라 못짜는 것이기 때문에 공부해야겠지...ㅎㅎ 같은 sort 함수 안에 lambda를 사용했는데 저렇게 줄일 수 있었다는 것을 생각 못했으니 말이다....

다른 코드도 내 코드와 살짝 섞어서 돌려봤는데 원래 내가 제출한 코드보다는 좀 더 오래 걸린 것들이 보였다.

def solution(numbers):
    answer = ''
    new_list = []
    for each in numbers:
        c = (str(each) * 4)[:4]
        length = len(str(each))
        new_list.append((c, length))

    new_list.sort(reverse = True)

    for each, length in new_list:
        answer += each[:length]

    if int(answer) == 0:
        return '0'

    return answer