가장 큰 수 만들기 - 숫자 조각을 이어붙이는 커스텀 비교 정렬 - 알고노트

숫자 조각을 이어붙여 가장 큰 수 만들기

작은 번호판 가게를 떠올려 봅시다. 상자에 숫자가 새겨진 금속 조각들이 있어요: [3, 30, 34, 5, 9]. 손님이 "이 조각들을 전부 한 줄로 붙여서, 만들 수 있는 가장 큰 번호를 만들어 주세요!"라고 합니다.

조각을 어떤 순서로 붙여야 가장 큰 수가 될까요?

함정 — "숫자 크기 순"은 틀린다

가장 먼저 떠오르는 생각은 "큰 숫자부터 붙이자"입니다. 숫자 크기 내림차순으로 정렬하면 34, 30, 9, 5, 3 → 3430953.

그럴듯해 보이지만 틀린 답입니다. 정답은 9534330이에요.

왜일까요? 9는 34보다 작은 숫자지만, 맨 앞에 9를 두면 첫 자릿수가 9가 되어 전체 수가 훨씬 커집니다. 즉 "조각의 숫자 값"이 아니라 "붙였을 때 어느 쪽이 더 큰가"가 진짜 기준입니다.

특히 헷갈리는 건 3과 30이에요. 둘 중 무엇을 앞에 둘까요?

• •3을 앞에: "3" + "30" = 330
• •30을 앞에: "30" + "3" = 303

330 > 303이므로 3이 앞서야 합니다. 숫자로는 30이 크지만, 붙여 보면 3이 먼저 와야 더 큰 수가 되는 거죠.

핵심 아이디어 — a+b vs b+a

여기서 정렬의 발상이 나옵니다. 두 조각 a, b의 순서를 정할 때, 숫자가 아니라 이어붙인 문자열을 비교합니다.

• •a + b 가 b + a 보다 크면 → a를 앞에
• •b + a 가 a + b 보다 크면 → b를 앞에

이 한 줄짜리 비교 규칙을 정렬의 기준(comparator)으로 꽂아 넣는 게 전부입니다.

왜 문자열 비교가 맞을까? a+b와 b+a는 항상 길이가 같습니다(두 조각을 합친 길이). 길이가 같은 두 수의 대소는 앞 자릿수부터 비교하면 되고, 그게 바로 문자열 사전순 비교와 정확히 일치하기 때문이에요.

몇 가지만 직접 대 보면 규칙이 손에 잡힙니다.

• •5 vs 9 → 59 vs 95 → 95가 크니 9가 앞
• •34 vs 5 → 345 vs 534 → 534가 크니 5가 앞
• •30 vs 34 → 3034 vs 3430 → 3430이 크니 34가 앞

이렇게 비교해 내림차순으로 정렬하면 조각 순서는 9, 5, 34, 3, 30이 되고, 모두 이어붙이면 9534330 — 정답입니다.

마지막으로 한 가지 함정만 더. 조각이 전부 0이면([0, 0]) 이어붙인 결과가 "00"이 되는데, 답은 "0" 하나여야 합니다. 정렬 후 맨 앞 글자가 '0'이면 "0"만 반환하면 깔끔하게 해결돼요.

정리하면 이런 흐름입니다.

1. 모든 조각을 문자열로 바꾼다

2. a+b vs b+a 비교로 내림차순 정렬한다

3. 정렬된 조각을 순서대로 이어붙인다

4. 맨 앞이 '0'이면 "0"만 반환한다

직접 눈으로 확인하기

조각들이 a+b vs b+a 비교(노랑)를 거쳐 자리를 바꾸고(빨강), 한 칸씩 최종 순서로 확정(초록)되는 전 과정을 단계별 시각화로 준비했습니다. 각 비교에서 "330" vs "303" 같은 문자열이 어떻게 승부를 가르는지 한눈에 보입니다.

👉 가장 큰 수 만들기 — 단계별 시각화로 풀이 보기

"왜 30보다 3이 먼저 와야 하지?"는 글로만 보면 헷갈리지만, 두 문자열이 나란히 비교되는 걸 한 번 보면 "아, 붙여서 큰 쪽이 이기는구나"가 단번에 이해됩니다.