[알고리즘] 프로그래머스 가장 큰 수 (Python)

---

programmers.co.kr/learn/courses/30/lessons/42746

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

문제 설명

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

 

CODE

def solution(numbers):
    res = []
    
    for number in numbers: 
        prev = str(number)
        add= list(str(number))

        i = 0
        while len(add) < 4:
            add.append(prev[i])
            i = (i + 1) % len(prev)
        add = int("".join(add))
        res.append([add, prev])

    res = sorted(res, reverse = True)
    return str(int("".join(unit[1] for unit in res)))

 

(코드 풀이)

주어진 정수 [6, 10, 2]를 사용해 풀이하면, 결과 값이 '6210'일 때 가장 큰 수가 된다.

여기서 나올 수 있는 경우의 수는 6210 외에도 6102, 2106, 2610, 1026, 1062 ('3!' 개) 가 있다. 이때, 가장 큰 수를 고르기 위한 아이디어는 정수를 모두 4자리로 만들어버리는 것이다. ([6, 10, 2]의 경우 ['6666', '1010', '2222']) 이를 내림차순 정렬해 크기가 큰 정수를 먼저 조합하면 가장 큰 수를 만들 수 있다. 

마지막으로, 결과 값은 문제의 지시에 따라 문자형으로 바꿔준다. (너무 큰 수가 나올 수 있기 때문에) 주의할 점은 문자로 바꾸기 전에 정수형으로 미리 변환해주어야 '0000'과 같은 경우를 알맞게 처리할 수 있다. ('0000' --> '0')

(원래는 수 하나씩 비교해 더해주려다가 한계를 깨닫고 웹서치의 도움을 받았다(^^..))

 

더 나은 코드

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

(출처: 프로그래머스 '가장 큰 수' -다른 사람의 풀이)

정렬 시 key를 써서 앞자리가 비슷해 모호한 경우를 보완해 준 것 같다. 이전 알고리즘 풀면서 람다 표현식에 대해 좀 공부해봤는데, 이런 식으로도 응용할 수 있다니!!

 

---

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 4학년 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)