[프로그래머스]가장 큰 수

[59] 가장 큰 수

책 구매하기

문제 정보

• 분류: 정렬
• 정답률: 52%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 커스텀 정렬, 문자열 비교, 이어붙이기, 가장 큰 수
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746

문제를 읽을 때 체크할 포인트

숫자 크기 자체가 아니라 이어 붙였을 때 어느 순서가 더 큰지를 비교해야 한다. 그래서 문자열 x, y에 대해 x+y와 y+x를 기준으로 정렬하는 발상이 핵심이다.

정렬 문제는 손이 바빠지기 전에 비교 기준부터 정리하는 게 먼저다. 어떤 값을 기준으로 한 번만 정렬하면 그다음 오히려 짧아지는 경우가 많다.

풀이 흐름

1. 모든 수를 문자열로 바꾼다.
2. 정렬 기준이 x+y와 y+x 비교가 되도록 정렬한다.
3. 이어 붙인 뒤, 전부 0인 경우만 예외 처리한다.

구현할 때 놓치기 쉬운 부분

숫자 자체의 크기가 아니라 이어 붙였을 때 어느 쪽이 더 큰지를 비교해야 한다. 단순 내림차순 정렬은 이 문제의 핵심을 반영하지 못한다.

파이썬 정답 코드

from functools import cmp_to_key

def solution(numbers):
  # 모든 수를 문자열로 바꾼다.
  strs = list(map(str, numbers))

  def compare(a, b):
    if a + b > b + a:
      return -1
    if a + b < b + a:
      return 1
    return 0

  strs.sort(key=cmp_to_key(compare))
  result = "".join(strs)
  # 정렬 기준이 x+y와 y+x 비교가 되도록 정렬한다.
  return "0" if result[0] == "0" else result

시간 복잡도

N은 numbers의 길이이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.