[프로그래머스] 정렬 - 가장 큰 수(파이썬 문제 풀이)

문제 링크

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

주어진 정수를 이어 붙여 가장 큰 수를 만들어내는 문제입니다. Level2 치고는 체감 난이도가 꽤 높았던 문제인 것 같습니다!

우선 입력 데이터인 numbers의 최대 길이가 100,000인 것으로 보아 상태 트리를 이용한 모든 경우의 수를 조합하는 방법은 아니라고 생각했습니다.

 

1. 파이썬에서 문자형으로 된 숫자를 비교할 때 자릿수에 상관없이 앞자리가 큰 수가 큰 것이다는 점을 활용해서 문제를 풀이했습니다.

a = '999'
b = '9888'
if a > b:
    print(a)
else:
    print(b)
# '999'

a = '999'
b = '9998'
if a > b:
    print(a)
else:
    print(b)
# '9998'

 

2. 하지만 단순히 문자형으로만 바꾸어 정렬하면 서로 다른 자릿 수를 비교할 때 합쳤을 때 더 작은 수가 앞으로 오게된다는 문제를 발견했습니다.

numbers = list(map(str, sys.stdin.readline().split()))
numbers.sort(reverse=True)
    print(numbers)
# ['9', '5', '34', '30', '3']
# 최대값을 만들기 위해선 3이 30 앞으로 와야함

 

3. 문제에서 "numbers의 원소는 0 이상 1,000 이하입니다."라는 조건에 따라 각 항목을 4자릿 수 이상으로 만들어 준 뒤 정렬하면 문제를 해결할 수 있습니다!

for i in range(len(numbers)):
	tmp = numbers[i]
	while len(tmp) < 4:
		tmp += tmp
	numbers[i] = tmp
numbers.sort(reverse=True)
print(numbers)
# ['9999', '5555', '3434', '3333', '3030']
# (원본 데이터) 3이 30 앞으로 오게 됐다!

 

4. 자릿 수 변환한 데이터, 원본 데이터를 하나의 리스트에 저장한 뒤 자릿 수 변환한 데이터를 기준으로 정렬하고 원본 데이터를 join해서 출력하면 원하는 결과가 나옵니다.

res = list()

for i in range(len(numbers)):
	tmp = numbers[i]
	while len(tmp) < 4:
		tmp += tmp
	
	res.append([tmp, numbers[i]])
res.sort(reverse=True)
print(str(int("".join(r[1] for r in res))))
# 9534330
# 마지막에 int로 한번 묶고 다시 str로 바꾸는 이유는 0만 여러개 들어올 경우 '0'으로 출력하기 위함

 

문제 풀이(파이썬)

---

def solution(numbers):
    numbers = list(map(str, numbers))
    res = list()

    for i in range(len(numbers)):
        tmp = numbers[i]
        while len(tmp) < 4:
            tmp += tmp

        res.append([tmp, numbers[i]])
    res.sort(reverse=True)
    return str(int("".join(r[1] for r in res)))

 

파이썬스러운 풀이 방법

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