[python] '가장 큰 수' - 프로그래머스 커뮤러닝 week1

문제

0 또는 양의 정수가 주어졌을 때, 정수를 이어붙여서 만들 수 있는 가장 큰 수를 만들자.

1. 해결방법 (Pseudo-code)

✏️ 첫 번째 해결방법

• 빈 문자열로 수를 초기화한다.
• 가장 크게 만들 수 있는 수를 고른다.
• 그 수를 현재 수에 이어 붙인다.
• 모든 수를 다 사용할 때까지 반복한다.

✏️ 두 번째 해결방법

• 빈 문자열로 수를 초기화한다.
• 수의 목록을 (크게 만드는 것 우선으로) 정렬한다.
• 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.
• 모든 수를 다 사용할 때까지 반복한다.

'크게 만드는 수'의 기준

• 길이가 서로 같을 경우, 수를 비교하면 된다.
• 길이가 서로 다를 경우, 자릿수를 감안하여 비교해야 한다.

알고리즘 설계 및 구현

• 대소 관계 비교를 위한 기준을 마련
• 이것을 이용하여 주어진 배열을 정렬
• 정렬된 배열을 이용하여 문자열 표현을 완성

2. 풀이

🔍 첫 번째 풀이

def solution(numbers):
	numbers = [str(x) for x in numbers]
    numbers.sort(key+lambda x : (x * 4)[:4], reverse=True) # 주어지는 정수의 길이는 1000이 최대
    묹ㄷㄱ = ''.join(numbers)
    return answer

🔍 두 번째 풀이

def solution(numbers):
	numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x : (x * 4)[:4], reverse=True)
    if numbers[0] == '0': # 첫번째 풀이에서는 0을 제외
    	answer = '0'
    else:
    	answer = ''.join(numbers)
    return answer

3. 복잡도

• numbers를 리스트로 받으므로, 들어있는 요소만큼 시간이 소요.
  = n에 비례 = (O)n

	numbers = [str(x) for x in numbers]

• 원소 간의 대소관계를 비교하며 배열의 길이가 n인 리스트의 요소를 sort하는 경우 = O(n log n)

	numbers.sort(key=lambda x : (x * 4)[:4], reverse=True)

• number의 크기를 다시 합쳐주는 것 = (O)n

	answer = ''.join(numbers)