[프로그래머스] 정렬 - 가장 큰 수 (python)

처음 문제를 읽을 때에는 쉬워보이는데 막상 풀어보면 이것저것 예외도 많고 어떤 방식을 써야할지 난감해 생각보다 어려웠다.

 

정렬 - 가장 큰 수, 문제 확인

문제 자체는 간단한데 양의 정수가 담긴 배열 numbers가 주어질 때, 가장 큰 수의 조합을 구하는 문제이다.

 

---

0 또는 양의 정수가 담긴 배열 numbers가 주어짐

순서를 재배치해 만들 수 있는 가장 큰 수를 문자열로 바꾸어 리턴

 

 

정렬 - 가장 큰 수, 문제 풀이

처음에는 별생각 안하고 자리수를 0으로 채워 맞춘 후에 큰 수대로 정렬, 하나씩 붙이면 된다고 생각했다. 그 중에 3, 30과 같이 같은 크기가 되는 경우는 실제 수 3, 30을 비교하는 방식으로 예외처리를 하는 방식으로 했다. 그런데 이렇게 하니 주어진 테스트케이스는 통과했지만 코드 채점 결과 전부 런타임에러가 뜨고 실패하는 상황이 발생했다. 반례를 찾아보니 [12,121]와 같은 것이 있었고 애초에 이런 방식으로 하면 안된다는 것을 알았다. 12,121의 경우 1210이 1200보다 더 크기때문에 12112가 되는데 실제로는 12121이 더 크기 때문이다.

 

(엉망인 코드이니 참고하지 않길 바란다...)

def solution(numbers):
    tmp=[]
    answer=''
    len_num=len(numbers)
    for v in numbers: #자릿수 맞추기
        if v<10 : tmp.append(v*1000)
        if 10<= v<100 : tmp.append(v*100)
        if 100<=v<1000 : tmp.append(v*10)
    sort_index=[i[0] for i in sorted(enumerate(tmp), key=lambda x:x[1])] #정렬되는 인덱스 순서를 기억
    count=0
    for i in range(len_num-1,-1,-1):
        v1=sort_index[i]
        v2=sort_index[i-1]
        if i==0 and count != len_num:
            answer+=str(numbers[v1])
        if tmp[v1]>tmp[v2]: # 큰 수를 먼저 붙이기
            answer+=str(numbers[v1])
            count+=1
        if tmp[v1]==tmp[v2]: # 같은 경우 예외처리
            count+=2
            if numbers[v1]>numbers[v2]: 
                answer+=str(numbers[v2])
                answer+=str(numbers[v1])
            else : 
                answer+=str(numbers[v1])
                answer+=str(numbers[v2])
        
    return answer

 

 

따라서 순서대로 붙일 경우 제일 큰 조합이 나오게끔 정렬을 하려면 어떻게 해야할까를 고민하던 중, 구글링에서 힌트를 얻어 자릿수를 맞추는 것이 아니라 숫자를 반복하게끔 해서 자릿수를 맞추는 방식으로 변경했다. 아까 든 예와 같이  [12,121]의 경우 숫자를 반복해서 자릿수를 맞추면 121212와 121121이 되고 121212가 더 크기 때문에 12121이라는 결과를 낼 수 있게 된다.

 

def solution(numbers):
    tmp=[]
    answer=''
    numbers = list(map(str, numbers)) # 전부 문자열로 변경
    for num in numbers: # 숫자 반복시켜 자릿수 맞추기
        len_num=len(num)
        if len_num==1 : tmp.append(num*6)
        if len_num==2 : tmp.append(num*3)
        if len_num==3 : tmp.append(num*2)
    sort_index=[i[0] for i in sorted(enumerate(tmp), key=lambda x:x[1])] # 정렬되는 인덱스 기억
    
    for i in range(len(numbers)-1,-1,-1): #큰 수대로 붙이기
        answer+=numbers[sort_index[i]]
    
    return answer

 

 

그런데 1~6은 여전히 런타임 에러가 발생했다. 

 

 

 

문제를 다시 살펴보니, numbers의 요소가 1000이하이기 때문에 1000일 경우 길이가 4이기 때문에 6자리가 아닌 12자리수로 맞춰주어 런타임 에러는 해결할 수 있었다. 그리고 마지막 테스트 11이 틀렸는데 질문하기에서 찾아보니 [0,0,0,0]일 때 0000이 아니라 0이 나와야 한다고 해서 해당 예외처리도 수행해주었다.

 

def solution(numbers):
    tmp=[]
    answer=''
    numbers = list(map(str, numbers))
    if numbers.count("0") == len(numbers) : return "0" #전부 0일 경우, "0"을 리턴
    
    for num in numbers:
        len_num=len(num)
        if len_num==1 : tmp.append(num*12)
        if len_num==2 : tmp.append(num*6)
        if len_num==3 : tmp.append(num*4)
        if len_num==4 : tmp.append(num*3)
    sort_index=[i[0] for i in sorted(enumerate(tmp), key=lambda x:x[1])]
    
    for i in range(len(numbers)-1,-1,-1):
        answer+=numbers[sort_index[i]]
    
    return answer

 

 

두 부분을 고쳐주니 테스트 케이스를 전부 통과할 수 있었다.