[알고리즘] 가장 큰 수

유동헌·2021년 9월 6일

1일1알고리즘

목록 보기

5/12

문제 설명

링크 : https://programmers.co.kr/learn/courses/30/lessons/42746

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

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

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

풀이 과정

내 식대로 해결해보려고 여러 방법을 사용했었지만, 결과적으로는 모두 실패했다. 검색을 통해 힌트를 얻은 후에먼저 문제를 해결하고 이 문제를 풀기 위해 알아야하는 문법을 공부하는 식으로 진행했었다.
코드에 대한 설명 후에, 내가 공부한 과정을 기록하였다.
https://weejw.tistory.com/315 문제를 이해하는데도, 푸는 대도 굉장히 많은 도움이 되었던 블로그...

def solution(numbers):
    answer = ''
    
    list = []
    
    for i in numbers:
        data_compare = (str(i) * 3)
        list.append([str(i), data_compare])
        
    data_result = sorted(list, key = lambda big : big[1], reverse = True)
    
    if data_result[0][0] == '0':
        return '0'
    
    for j in data_result:
        answer += j[0]

lambda를 사용한 정렬

눈으로 보기만 했었는데 이번에 공부, 사용까지 하게되었다. 사실 이 문제에서 키 포인트라고 생각된다. 밑에서 기술하겠지만 lambda를 사용하여 세 자리 수까지 정렬하는 방법을 사용하지 않고서는 푸는 방법을 아직도 잘 모르겠다.
첫 번째 for loop를 찍어보면,
```
    for i in numbers:
        data_compare = (str(i) * 3)
        list.append([str(i), data_compare])
				print(list)

# 출력
[['3', '333']]
[['3', '333'], ['30', '303030']]
[['3', '333'], ['30', '303030'], ['34', '343434']]
[['3', '333'], ['30', '303030'], ['34', '343434'], ['5', '555']]
[['3', '333'], ['30', '303030'], ['34', '343434'], ['5', '555'], ['9', '999']]
```
이런 식의 결과가 나온다. 3이라는 인자를 문자열로 바꾼 후 3을 곱해준다. 왜냐하면 문제에서 원소의 길이가 1,000이하라고 했기 때문이다. 세 번째 자리 수까지 비교를 하려고 위와 같은 방식으로 data_compare를 만들어준다. 그리고 한 쌍으로 묶어서, 리스트 안에 리스트로 요소를 짚어 넣는다. (3, 30, 34 등의 요소를 비교하려고 하는 것)

그리고 lambda 정렬을 이용한다.

data_result = sorted(list, key = lambda big : big[1], reverse = True)

각 요소의 [1] 인덱스 값으로 정렬한다. 그러면 자연스럽게 앞 자리, 뒤 자리까지 정렬이 된다. 자동으로 그렇게 된다. 가장 큰 수가 앞으로 나온다.

생각의 과정

일단 앞서 기술한 풀이 방법은 블로그를 보고 나름의 공부를 한 뒤에, 내 것으로 만드는 작업이었다면, 블로그 보기 전에 스스로 풀어보려고 굉장히 많은 노력을 했다. 그랬으나.. 실패했다.
for loop 돌려서 하나씩 꺼내는 방법을 생각했었고,
```
for i in range(len(numbers)):
    if str(numbers[i])[0] == "9":
        answer += str(numbers[i])
    if str(numbers[i])[0] == "8":
        answer += str(numbers[i])
print(answer)
```
이런 식으로 앞 자리가 9면 앞으로 오고, 그 다음 8... 하지만 이런 방법으로 했을 때 99, 98이 비교가 되질 않았다. 그래서 리스트의 순서대로 그냥 answer에도 그대로 담겨 버리는 문제가 발생했다.
자리 수가 문제가 된다면, 같은 자리 수끼리 묶어서 하면 될 거 같은데?라고 생각해서,
```
numbers = [6, 10, 2, 99]

dic = {number : len(str(number)) for number in numbers}

print(dic)

sort_dic = sorted(dic.keys(), reverse=True)

print(sort_dic)

출력
{6: 1, 10: 2, 2: 1, 99: 2}
[99, 10, 6, 2]
```
자리수가 문제인 것 같아서 자리수까지 같이 구해서 정렬을 하면 되지 않을까 했는데 이렇게 해도 안된다. 자리수는 다르더라도, 가장 큰 수를 구하기 위해서는 98 : 2, 9 : 1이라도 9가 먼저 나와야 하기 때문이다... 이쯤에서 포기하고 힌트를 봤다.

lambda 공부

a = [5,4,1,9,10]
b = sorted(a, reverse=True)
print(b)

a = [(1, 2), (0, 1), (5, 1), (5, 2), (3, 0)]

# key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다.

b = sorted(a)

# 리스트 안에, [0] 값으로 정렬
c = sorted(a, key = lambda x : x[0])
e = sorted(a, key = lambda x : x[0], reverse=True)

# 리스트 안에, [1] 값으로 정렬
d = sorted(a, key = lambda x : x[1])

a1 = [(1, 3), (0, 3), (1, 4), (1, 5), (0, 1), (2, 4)]
f = sorted(a1, key = lambda x : (x[0], -x[1]))

print(c)
print(d)
print(e)
print(f)

b1 = [(6, 1), (1, 6), (5, 2), (2, 5), (4, 3), (3, 4)]
f1 = sorted(b1, key = lambda x : (x[0], -x[1]))

print(f1)

# sorted의 key 인자로 내가 커스텀할 비교 함수를 보내주면 된다
# 비교 함수는 비교할 아이템의 요소를 반환하면 된다
# 비교 함수는 익명 함수도 가능하고 별도로 정의해도 된다
# 비교할 아이템의 요소가 복수 개일 경우 튜플로 그 순서를 내보내주면 된다

data = ["나라","가구","봄","가을","도토리","낫","혹","가을 아침","나는 밥을 먹고 있다."]

data.sort(key = lambda x:(len(x), x))
print(data)

# 딕셔너리 정렬
money = {
    "백원" : 100, 
    "1$" : 1200, 
    "10$" : 12000, 
    "오천원" : 5000, 
    "만원" : 10000, 
    "100$" : 120000, 
    "오만원" : 50000
    }

money = sorted(money.items(), key = lambda x : x[1])

print(money)

# 출력
[10, 9, 5, 4, 1]
[(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]
[(3, 0), (0, 1), (5, 1), (1, 2), (5, 2)]
[(5, 1), (5, 2), (3, 0), (1, 2), (0, 1)]
[(0, 3), (0, 1), (1, 5), (1, 4), (1, 3), (2, 4)]
[(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)]
['낫', '봄', '혹', '가구', '가을', '나라', '도토리', '가을 아침', '나는 밥을 먹고 있다.']
[
('백원', 100), 
('1$', 1200), 
('오천원', 5000), 
('만원', 10000), 
('10$', 12000), 
('오만원', 50000), 
('100$', 120000)
]

참고 블로그 : https://hyun-am-coding.tistory.com/entry/key와-lambda를-이용한-정렬

후기

일단 도저히 해결이 안될 거 같아서 힌트를 보고, 블로그를 뒤져보고 해결했지만.. 공부는 많이 한 것 같다.

유동헌

지뢰찾기 개발자

이전 포스트

[알고리즘] 정수제곱근 판별

다음 포스트