가장 큰 수

하루히즘·2021년 6월 16일
0

프로그래머스

목록 보기
13/17

설명

프로그래머스의 가장 큰 수 문제다.

주어진 정수를 조합하여 만들 수 있는 가장 큰 수를 반환하는 문제로 예를 들어 [6, 10, 2]가 주어진다면 여러 조합이 있을 수 있겠지만 6210이 가장 큰 수의 조합이 된다. 입력값은 1에서 1000 사이의 숫자가 최대 100,000개 주어질 수 있기 때문에 조합 결과는 정수가 아닌 문자열로 반환해야 한다.

풀이

불가능한 재귀 탐색, 단순 정렬

숫자가 100,000개나 주어질 수 있기 때문에 재귀 탐색을 통한 문자열 조합 및 비교는 불가능하다. 그래서 처음 생각했던 방법은 주어진 숫자들을 정렬해서 큰 순서대로 조합하는 방법이었다.

그러나 문제에서는 한 자리 숫자부터 네 자리 숫자까지 주어질 수 있기 때문에 [3, 300]이 있으면 300과 3 순서대로 조합해서 3003을 만들게 된다. 하지만 제일 큰 조합은 3과 300 순서대로 조합한 3300이다. 그러므로 단순 정렬로는 풀 수 없었다.

문자열 패딩

결국 인터넷에서 해설을 검색해서 풀 수 있었는데 특이하게 주어진 숫자를 문자열로 바꿔서 4개 정도 이어붙여서 정렬하는 방법이었다.

def solution(numbers):
    # 주어진 숫자를 문자열로 바꿔서 4번 반복해서 조합한 후 튜플로 리스트에 저장.
    comparing_numbers = [(str(number), str(number) * 4) for number in numbers]
    # 조합된 문자열을 기준으로 내림차순 정렬.
    compared_numbers = sorted(comparing_numbers, key=lambda x: x[1], reverse=True)
    # 정렬된 문자열을 조합한 후 정수로 변환한 후 다시 문자열로 변환.
    return str(int("".join([compared_number[0] for compared_number in compared_numbers])))

대체 왜 이렇게 해서 풀리는 건지 이해가 가지 않았지만 문제에서 어떤 정렬을 요구하는지, 파이썬에서 문자열을 어떻게 정렬하는지 찾아보니 이해할 수 있었다.

먼저 문제의 예시를 다시 보면 주어진 숫자들이 다음처럼 정렬되는 것을 볼 수 있다.

  • [6, 10, 2] => [6, 2, 10] => "6210"
  • [3, 30, 34, 5, 9] => [9, 5, 34, 3, 30] => "9534330"

주어진 숫자를 정렬할 때는 일반적인 정수나 문자열 비교가 아니라 한 글자씩 비교해서 첫 번째 글자를 기준으로 먼저 정렬하고 만약 같은 숫자가 있다면 다음 글자를 이용해서 비교해야 한다. 34, 30을 예로 들면 두 정수는 "34", "30"으로 치환될 수 있으며 첫 번째 글자는 "3"으로 동일하다. 그래서 두 번째 글자인 "4"와 "0"을 비교하면 4가 더 크기 때문에 "34"가 "30"보다 높은 우선순위를 가진다고 판단할 수 있다.

그런데 3, 30은 어떨까? "3", "30"도 첫 글자는 "3"으로 동일하다. 그렇기 때문에 두 번째 글자를 이용해서 비교해야 하는데 "3"은 두 번째 글자가 없기 때문에 비교할 수 없다. 그럼 어떻게 "3"이 "30"보다 더 우선순위가 높다고 판단할 수 있을까?

해설에서 제공하는 창의적인 방법은 바로 모든 숫자를 반복해서 이어붙여서 아래처럼 패딩하는 방식이었다.

  • 3 -> "3" * 4 -> "3333"
  • 30 -> "30" * 4 -> "30303030"

문제에서는 1부터 최대 1,000까지의 정수가 주어진다고 명시하고 있다. 그렇기 때문에 한 자릿 수가 나와도 4자리 정수와 비교할 수 있도록 4번 반복하는 방식으로 패딩하여 문자열로 만드는 것이다.

4자리로 만들기 위해서라면 그냥 '0'을 세 번 붙여서 그냥 4자리로 만들 수도 있지만 "3000"과 "30000"은 "30000"이 더 크다고 판단된다. 그렇기 때문에 '0'이 아니라 원래 숫자를 반복해서 "3333"과 "30303030"으로 비교한다면 "3333"이 더 크다고 판단하여 3을 30보다 먼저 정렬할 수 있다.

파이썬의 문자열, 정수 정렬

결론만 먼저 얘기했지만 그러면 대체 왜 이렇게 비교되는 것일까? 이는 파이썬에서 정수와 문자열을 정렬하는 것의 차이를 보면 알 수 있다.

>>> sorted(['3333', '30303030'])
['30303030', '3333']
>>> sorted([3333, 30303030])
[3333, 30303030]

문자열 "3333"과 "30303030"을 비교했을 때는 "3333"이 더 크다고 나왔지만 정수 3333과 30303030을 비교했을 때는 당연히 30303030이 더 크다고 정렬된 것을 볼 수 있다. 왜 문자열에서는 결과가 반대로 나온 것일까?
이는 파이썬에서 문자열을 비교할 때 위처럼 한 문자씩 비교하기 때문이다. 위의 "3333"과 "30303030"을 비교해 보면 먼저 첫 글자는 "3"으로 동일하다. 하지만 다음 글자에서 "3333"의 "3"이 "30303030"의 "0"보다 더 크기 때문에 여기서 비교는 중단되고 "3333"이 더 크다고 판단하게 된다.

문자열이 얼마나 길든 한 글자씩 비교했을 때 더 큰 쪽이 나왔다면 비교가 끝나는 것이다. 반대로 "123"과 "12345"를 비교해보면 이번에는 둘 다 "12345"가 더 크다고 판단되는 것을 볼 수 있다.

>>> sorted(["123", "12345"])
['123', '12345']
>>> sorted([123, 12345])
[123, 12345]

이 때는 "123"과 "12345"를 세 번째 글자까지 비교해도 전부 동일하기 때문에 문자가 좀 더 많은 "12345"가 더 크다고 판단된 것이다. 알기 쉽게 비교해보면 다음과 같다.

>>> ["1","2","3", "", ""] < ["1","2","3","4","5"]
True
>>> "" < "4"
True
>>> "" < "5"
True

문제에서 요구하는 정렬

이 문제는 프로그래머스에서 정렬 문제에 분류되어 있다. 그럼 문제에서 요구하는 최대 값으로 조합하는 방법은 어떻게 탐색할 수 있을까? 주어지는 정수는 1에서 1,000 사이로 주어질 수 있기 때문에 비교 대상은 한 자리 문자부터 네 자리 문자열까지 다양하다.

언급했듯이 "34"와 "30"은 "34"가 더 우선순위가 높아야 하지만 "3"과 "30"은 "3"이 더 우선순위가 높아야 한다. 왜냐면 "30"의 두 번째 글자인 "0"이 "3"보다 작기 때문에 "303"으로 조합되면 안되기 때문이다.

물론 "3"과 "34"는 "34"가 더 우선순위가 높아야 한다. 이 때는 "334"가 아니라 "343"으로 조합되어야 하기 때문이다. 여기서 눈치챌 수 있는 점은 중복된 서로 다른 길이의 숫자 문자열을 비교할 때 비교 대상("34")의 다음 글자("4")가 자신("3")의 이전 글자("3")보다 크면 더 우선순위가 높다고 판단하는 것이다.

비슷하게 "3"과 "30"도 비교 대상("30")의 다음 글자("0")가 자신("3")의 이전 글자("3")보다 작기 때문에 "30"보다 "3"이 더 우선순위가 높다고 판단한다. 왜냐면 다음 글자가 자신보다 커야 자기보다 앞에 조합했을 때 더 큰 결과를 얻을 수 있기 때문이다.

좀 더 긴 예로 "1231"과 "123"이 있을 때 비교 대상("1231")의 다음 글자("1")는 자신("123")의 이전 글자("3")보다 작기 때문에 자신이 우선순위가 더 높아야 한다. 그래서 "1231231"이 되어야 하지 "1231123"이 되선 안되는 것이다.

그리고 이런 다음 글자, 이전 글자를 비교하는 방법으로 위에서 숫자 문자열을 4번 반복해서 이어붙이는 방법과 문자열 비교 로직을 활용한 것이다.

후기

사실 풀이를 보고 어찌저찌 이해하긴 했지만 실제로 이런 문제가 나오면 혼자는 못 풀 것 같다. 참 이상하지만 신기한 문제였다.

참고

파이썬 풀이 원본

profile
YUKI.N > READY?

0개의 댓글