가장 큰 수

출처: 프로그래머스

주소: https://programmers.co.kr/learn/courses/30/lessons/42746#

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

[문제 설명]

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 만드는 문제

 

[예시]

예시

[제한 사항]

 - numbers의 원소는 0이상이고 1,000이하의 숫자

 - numbers의 길이는 1이상이고 100,000이하의 리스트

 - return 값은 문자열로 출력

 

[알고리즘]

 1) numbers의 각 숫자들을 문자로 변경

 2) 각 숫자들의 길이를 4개가 되도록 변경

    - numbers의 원소가 0 이상이고 1000이하의 숫자이기 때문에

    - 2번째 예시에서 볼 수 있듯이, 3보다 30이 뒤에 있고 3보다 34가 앞에 있다.

    - 따라서, 아래의 규칙이 만족되도록 변경

    - (1) 길이가 1인 경우: 길이가 4개가 되도록 이어 붙인다.

        ex) 3인 경우 => 3333

    - (2) 길이가 2인 경우: 문자로 변경된 숫자를 이어 붙여서 4개가 되도록 한다.

        ex) 32인 경우 => 3232

    - (3) 길이가 3인 경우: 문자로 변경된 숫자에 문자로 변경된 숫자의 첫번째 문자를 이어 붙여서 4개가 되도록 한다. 

        ex) 321인 경우 => 3213   

    - (4) 길이가 4인 경우: 문자로 변경된 숫자를 그대로 사용

        ex) 1000인 경우 => 1000

 

 3) 각 길이가 4개로 변경된 문자와 원래 문자 길이를 리스트에 저장

 4) 리스트를 문자를 기준으로 내림차순으로 정렬

 5) 정렬된 순서대로 문자를 원래 문자 길이만큼만 슬라이스하여 정답에 이어붙인다.

 6) 예외처리 -> n개의 0이 나오면 0....0으로 나오게 되는데, 이 부분을 0으로 변경해준다.

 

[전체 코드]

def solution(numbers):
    answer = ''
    items = []
    for number in numbers:
        # 1자리
        if 0 <= number <= 9:
            items.append([str(number) * 4, 1])
        # 2자리
        elif 10 <= number <= 99:
            items.append([str(number) + str(number), 2])
        # 3자리
        elif 100 <= number <= 999:
            items.append([str(number) + str(number)[0], 3])
        # 4자리 => 1000
        elif number == 1000:
            items.append([str(number), 4])
    
    # 정렬
    items = sorted(items, key=lambda x:x[0], reverse=True)
    
    # 정답 삽입
    for item, size in items:
        answer += item[:size]
    
    # 예외 처리
    if int(answer) == 0:
        answer = '0'
    
    return answer

[느낀점]

처음에는 모든 경우의 수를 따지기 위해, 조합을 사용해서 결과를 도출하였다.

하지만, 너무 오래 걸리기 때문에 다른 방법을 찾다가 30이 3보다 작은 걸 알게 되고 전체 길이를 맞춰서 정렬을 하고 정답을 도출하니 정답을 맞추게 되었다.

항상 모든 경우를 따지는 거는 하지 않는 것이 좋을 것 같다.