[코딩테스트] 가장 큰 수

프로그래머스 lv.2 가장 큰 수 문제를 풀어보았다.

 

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

프로그래머스

나한테 lv.2 문제는 너무 어려운것 같다 ㅜㅜ

 

 

처음에 짰던 코드이다.

def solution(numbers):
    answer = ''
    
    while numbers:
        maxi = str(numbers[0])
        idx = 0
        
        for i in range(len(numbers)):
            
            if len(maxi) == min(len(maxi), len(str(numbers[i]))):
                minArr = maxi
                maxArr = str(numbers[i])
                minIdx = idx
                maxIdx = i
            else:
                maxArr = maxi
                minArr = str(numbers[i])
                minIdx = i
                maxIdx = idx
        
            for j in range(len(minArr)):
                if minArr[j] != maxArr[j]:
                    if minArr[j] > maxArr[j]:
                        maxi = minArr
                        idx = minIdx
                        break
                    elif minArr[j] < maxArr[j]:
                        maxi = maxArr
                        idx = maxIdx
                        break
                        
                if j+1 == len(minArr) and len(minArr) != len(maxArr):
                    if minArr[j] < maxArr[j+1]:
                        maxi = maxArr
                        idx = maxIdx
                    else:
                        maxi = minArr
                        idx = minIdx
                                                
        answer += str(numbers[idx])
        numbers.pop(idx)
    answer = str(int(answer))
    
    return answer

 

주어진 테스트 케이스는 모두 해결하는 것 같긴 했는데 시간 초과가 나왔다 ㅜㅜ. 들어가는 배열의 범위가 굉장히 커서 시간복잡도 O(n^2) 으로 코드가 돌아가면 너무 오래 걸리는것 같다.

 

코드는 배열을 순회하면서 사전순으로 가장 큰 수를 찾고 answer문자열에 붙인 후, 해당 수를 numbers 배열에서 제거한다. numbers 배열에 남은 수가 없을때까지 반복을 진행한다.

사전순으로 배열하는 알고리즘은 일단 두 수를 비교할때 (1)같은 인덱스의 숫자가 다르다면 더 큰쪽을 선택하고 (2)같은 인덱스의 숫자가 같고 한 수의 그 다음 인덱스의 숫자가 더 크면 그쪽을 선택한다.

 

 

 

대부분의 경우를 직접 케이스를 분류해서 코드를 짰기 때문에 코드도 길고 loop도 많이 돌아서 시간초과도 뜬다. 총체적 난국이다. 아래는 그 이후 힌트를 보고 다시 짠 코드이다.

 

def solution(numbers):
    answer = ''
    
    numStr = []
    for i in numbers:
        numStr.append(str(i))
        
    numStr.sort(key=lambda x: x*3, reverse=True)
    
    for i in numStr:
        answer += i
    
    answer = str(int(answer))
    return answer

 

배열의 원소가 0 ~ 1000 까지 들어오므로 문자열로 변환된 숫자를 연달아 세번 붙인 상태에서 비교하여 정렬하는게 이 코드의 아이디어이다. 코드로 구현하는 것은 어렵진 않지만 미친 발상이다. 이걸 내가 코테에서 떠올릴 수 있을지 의문이다.

 

 

다른 정답들을 둘러보니 a, b 가 있을때 ab 와 ba 를 비교해서 더 큰 수를 찾는 알고리즘도 있었다. 이것도 굉장히 좋은 아이디어 인것 같다.