가장 큰 수

문제

첫 번째 풀이

def solution(numbers):
    from itertools import permutations

    L = []
    for n in numbers:
        L.append(str(n))
    answer = ''
    
    L = sorted(L, reverse=True)
    # print(L)
    #  ['9', '5', '34', '30', '3', '20', '2']

    totalL = []
    X = []
    for i in range(len(L)):
        X.append(L[i])

        if i == len(L)-1:
            totalL.append(X)
            break

        if L[i][0] != L[i+1][0]:
            totalL.append(X)
            X = []
        
    # print(totalL)
    # [['9'], ['5'], ['34', '30', '3'], ['20', '2']]

    for x in totalL:
        if len(x) == 1:
            answer += x[0]
            # print("answer = ", answer)

        else:
            result = []
            perL = list(permutations(x,len(x)))
            for a in perL:
                strr = ''
                for num in a:
                    strr += str(num)
                result.append(strr)
            maxVal = 0
            for a in result:
                a = int(a)
                if maxVal < a:
                    maxVal = a
            answer += str(maxVal)
    return answer

첫 번째 자리를 기준으로 나눠서 (첫 번째 자리가 같은 숫자들끼리 나눠서) 그게 길이가 1이면 그냥 answer에 넣고 1이 아니면 그 배열에서 뽑을 수 있는 모든 경우를 구한다(순열) 그 나올 수 있는 모든 조합에서 가장 큰 수를 구하고 answer 에 더해준다.

순열을 구하는 과정에서 시간초과가 날거라고 생각은 했지만 이 방법밖에 모르겠더라

두 번째 풀이

주어진 조건 중에

numbers의 원소는 0 이상 1,000 이하입니다.

이 부분이 핵심이었던 것 같다.

풀이 참고)

문자열 길이를 3배로 늘린 후에 비교하는 방식 ( 원소가 1000이하이므로 )
-> 핵심 아이디어

문자열에서의 대소비교와 일반숫자의 대소비교가 다르기 때문에 가능한 코드.
문자열 비교 연산의 경우에 문자열 첫 번째 인덱스를 아스키 숫자로 바꿔서 비교하고, 같으면 그 다음 인덱스를 비교하기 때문에 숫자 비교와는 다르다.

예를들어 '121'과 '12'의 경우 12가 더 먼저 와야 큰수를 만들 수 있는데, 문자열 비교에서 '121121121'과 '121212'가 더 큰수이기 때문이다.

따라서 비교 하는 숫자들의 자리수를 맞춰서 비교를 해보기 위해 문자열 곱셈을 하여 숫자의 길이를 늘렸다.

3 ----> 3 3 3 |
31 ---> 3 1 3 | 1 3 1
310 --> 3 1 0 | 3 1 0 3 1 0

출처 - https://huidea.tistory.com/4

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

int -> str 의 과정을 안해주면 테스트 케이스 1개가 삐꾸나는데 이건 000인 경우이다.

key = lambda x : x*3, 이 생각을 못한다면 시간 제한 안에는 죽어도 못풀었을거라 생각했다. 지금까지 풀었던 문제들 중에 풀이과정이 제일 신박했다.

---

for n in numbers:
    L.append(str(n))

위의 코드는 아래와 같이 바꿀 수 있다. map 쓰는 거 자꾸 까먹는다.

numbers = list(map(str, numbers))