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

[프로그래머스][LV.2] 가장 큰 수 | python3

2025. 3. 11. 19:25ㆍ프로그래머스/LV.2

문제설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한조건

- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

문제풀이

숫자들을 문자열로 바꾼다음 내림차순으로 정렬한 후 합치면 될 거라고 생각했다, 근데 "[3, 30, 34, 5, 9]" 이런 경우 30이 3보다 먼저 나와서 틀린 값을 리턴하게 됨.

def solution(numbers):
    
    strnum=[]
    for num in numbers:
        strnum.append(str(num))
    strnum.sort(reverse=True)
    answer=''.join(strnum)
    return answer

이 방법이 안되면 어떤 방법으로 풀어야 할까...

다른 사람 코드를 살짝 참고했다. lambda함수를 활용해서 x에 3을 곱해준다 ( 원소가 1000이하이기 때문에 3을 곱해주는 듯) 곱해준 값으로 비교를 해서 정렬한 후 합친다.

def solution(numbers):
    
    strnum=[]
    for num in numbers:
        strnum.append(str(num))
    # x에 3을 곱해주면 문자열이기 때문에 3은 333, 30은 303030이 됨. 이걸 정렬하면 333이 더 크므로 3이 더 앞에 나오게 됨
    strnum.sort(key=lambda x: x*3, reverse=True)
    answer=''.join(strnum)
    return answer

11번 하나가 틀렸다.....

입력값 => [0, 0, 0]
기댓값 => "0"

=> 이런경우인듯.

나의코드

def solution(numbers):
    
    strnum=[]
    # print(set([0,0,0]))
    if set(numbers) == {0}:
        return '0'
    for num in numbers:
        strnum.append(str(num))
    # x에 3을 곱해주면 문자열이기 때문에 3은 333, 30은 303030이 됨. 이걸 정렬하면 333이 더 크므로 3이 더 앞에 나오게 됨
    strnum.sort(key=lambda x: x*3, reverse=True)
    answer=''.join(strnum)
    return answer

참고하기

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

int를 해주어서 000 일 경우의 수를 제거. (int를 하면 0이 됨)

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

from io import StringIO


def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj

        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0

        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0

        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0

        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0

        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0

        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K


def comparator(x, y):
    x = str(x)
    y = str(y)
    x_y = int(x + y)
    y_x = int(y + x)

    if x_y < y_x:
        return -1
    elif y_x < x_y:
        return 1
    else:
        return 0


def solution(numbers):

    numbers = sorted(numbers, key=cmp_to_key(comparator), reverse=True)

    string_buffer = StringIO()
    for number in numbers:
        string_buffer.write(str(number))

    answer = int(string_buffer.getvalue())
    return str(answer)

두 가지 풀이 방법은 "가장 큰 수" 문제를 해결하는 코드로, 주어진 숫자 배열을 조합하여 만들 수 있는 가장 큰 숫자를 문자열 형태로 반환하는 방식입니다. 두 풀이 모두 사용자 정의 비교 함수 (comparator) 를 사용하여 정렬 방식을 커스텀하는 것이 핵심입니다.

🔹 첫 번째 풀이: functools.cmp_to_key를 이용한 정렬

import functools

def comparator(a, b):
    t1 = a + b
    t2 = b + a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) # t1이 크면 1, t2가 크면 -1, 같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]  # 숫자를 문자열로 변환
    n = sorted(n, key=functools.cmp_to_key(comparator), reverse=True)  # 사용자 정의 정렬 적용
    answer = str(int(''.join(n)))  # 리스트를 문자열로 합친 후, 정수 변환 후 다시 문자열로 변환
    return answer

🔍 풀이 과정

숫자를 문자열로 변환
- 숫자는 자리수를 고려해서 정렬해야 하므로, 문자열로 변환합니다.
- 예: [3, 30, 34, 5, 9] → ['3', '30', '34', '5', '9']
사용자 정의 비교 함수(comparator)를 이용한 정렬
- 두 숫자를 문자열로 합쳐서 비교하는 방식입니다.
- 예:
  - a = "3", b = "30"
  - t1 = "330", t2 = "303"
  - "330" > "303" 이므로 t1이 더 크므로 1 반환
정렬 후 문자열 결합
- 정렬된 리스트를 ''.join(n)으로 문자열로 변환
- "000"과 같은 경우를 방지하기 위해 int()로 변환 후 다시 str()로 변환

✅ 핵심 포인트

functools.cmp_to_key()를 사용하여 comparator를 key 함수로 변환
두 숫자를 이어붙인 후 비교하여 정렬하는 방식

🔹 두 번째 풀이: 직접 cmp_to_key 구현

from io import StringIO

def cmp_to_key(mycmp):
    """ 비교 함수를 key 함수로 변환 """
    class K:
        def __init__(self, obj, *args):
            self.obj = obj

        def __lt__(self, other): return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other): return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other): return mycmp(self.obj, other.obj) == 0
        def __le__(self, other): return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other): return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other): return mycmp(self.obj, other.obj) != 0
    return K

def comparator(x, y):
    """ 사용자 정의 비교 함수 """
    x, y = str(x), str(y)
    x_y, y_x = int(x + y), int(y + x)

    if x_y < y_x:
        return -1
    elif y_x < x_y:
        return 1
    else:
        return 0

def solution(numbers):
    numbers = sorted(numbers, key=cmp_to_key(comparator), reverse=True)

    string_buffer = StringIO()
    for number in numbers:
        string_buffer.write(str(number))

    answer = int(string_buffer.getvalue())  # "000"과 같은 경우를 방지
    return str(answer)

🔍 풀이 과정

직접 cmp_to_key 구현
- cmp_to_key()는 comparator를 key 함수로 변환하는 역할을 합니다.
- __lt__, __gt__, __eq__ 등의 비교 연산자를 직접 정의하여 Python의 sorted()에서 사용할 수 있도록 변환
사용자 정의 비교 함수 (comparator)
- 두 숫자를 이어붙였을 때 더 큰 숫자가 앞에 오도록 정렬
- x + y와 y + x를 비교하여 정렬 순서를 결정
StringIO를 이용한 문자열 결합
- ''.join() 대신 StringIO()를 사용하여 성능을 최적화
- 정렬된 숫자를 하나씩 string_buffer에 추가하여 문자열을 만들고 int()로 변환 후 다시 문자열 변환

✅ 핵심 포인트

cmp_to_key를 직접 구현하여 비교 함수를 sorted()의 key로 변환
StringIO를 이용해 문자열 결합 속도 최적화

🔥 두 풀이 비교

첫 번째 풀이 두 번째 풀이

cmp_to_key 사용	functools.cmp_to_key() 사용	직접 구현
정렬 방식	sorted(n, key=functools.cmp_to_key(comparator), reverse=True)	sorted(numbers, key=cmp_to_key(comparator), reverse=True)
문자열 결합 방식	''.join(n) 사용	StringIO() 사용
가독성	✅ 간결하고 직관적	❌ 비교적 복잡
성능 최적화	❌ 일반적인 문자열 연결	✅ StringIO() 사용으로 성능 개선
유지보수성	✅ 표준 라이브러리 사용으로 유지보수 쉬움	❌ 직접 구현한 cmp_to_key로 유지보수 부담

🚀 결론

첫 번째 방법이 더 간결하고 직관적이므로 일반적인 경우에 적합
두 번째 방법은 StringIO를 활용한 성능 최적화가 되어 있어, 매우 큰 숫자 배열을 다룰 때 유리할 수 있음

👉 일반적으로는 첫 번째 풀이를 사용하는 것이 좋으며, 성능 최적화가 필요할 경우 두 번째 방식을 고려하면 됩니다!

1️⃣ sorted() 함수

sorted(iterable, key=None, reverse=False)

iterable: 정렬할 데이터(리스트 등)
key: 정렬 기준을 정하는 함수
reverse: True면 내림차순 정렬, False면 오름차순 정렬

💡 sorted()는 기본적으로 오름차순 정렬을 수행하지만, key를 활용하면 사용자 정의 정렬 기준을 적용할 수 있어!

2️⃣ cmp_to_key()의 역할

Python 2에서는 sorted()에 비교 함수(cmp)를 직접 전달할 수 있었지만, Python 3에서는 비교 함수 대신 정렬 기준 함수(key)를 전달해야 해.
💡 cmp_to_key()는 비교 함수(cmp)를 정렬 기준 함수(key)로 변환해주는 역할을 해!

import functools

def comparator(a, b):
    t1, t2 = a + b, b + a
    return (int(t1) > int(t2)) - (int(t1) < int(t2))  # a + b가 크면 1, 작으면 -1, 같으면 0 반환

key_function = functools.cmp_to_key(comparator)

comparator(a, b)는 두 문자열을 이어붙인 결과를 비교하는 함수
cmp_to_key(comparator)를 적용하면, 정렬을 위한 key 함수가 생성됨

3️⃣ 핵심 코드 분석

n = sorted(n, key=functools.cmp_to_key(comparator), reverse=True)

🔹 sorted(n, key=functools.cmp_to_key(comparator)) 동작 과정

리스트 n
```
n = ["3", "30", "34", "5", "9"]
```

정렬 기준(comparator) 적용

각 원소를 비교하여 정렬 기준을 결정함

예제 비교 과정:

"3" vs "30" → "330" > "303" → "3"이 앞
"34" vs "3" → "343" > "334" → "34"가 앞
"5" vs "34" → "534" > "345" → "5"가 앞
"9" vs "5" → "95" > "59" → "9"가 앞

정렬 결과 (오름차순): ["30", "3", "34", "5", "9"]

reverse=True 적용
- 내림차순으로 변경: ["9", "5", "34", "3", "30"]

4️⃣ 실행 예제

import functools

def comparator(a, b):
    t1, t2 = a + b, b + a
    return (int(t1) > int(t2)) - (int(t1) < int(t2))  # t1이 크면 1, t2가 크면 -1, 같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]  # 숫자를 문자열로 변환
    n = sorted(n, key=functools.cmp_to_key(comparator), reverse=True)  # 사용자 정의 정렬 적용
    return str(int("".join(n)))  # 문자열 합치기 후 정수 변환(앞의 0 제거)

print(solution([3, 30, 34, 5, 9]))  # "9534330"

📌 9534330이 나오는 이유?

정렬된 리스트: ["9", "5", "34", "3", "30"]
''.join(n): "9534330"

🔥 정리

n = sorted(n, key=functools.cmp_to_key(comparator), reverse=True)

✅ comparator를 이용해 문자열 이어붙이기 기준으로 정렬
✅ cmp_to_key(comparator)로 비교 함수를 key 함수로 변환
✅ reverse=True를 적용해 내림차순 정렬

📌 이 코드의 핵심은 "두 숫자를 이어붙였을 때 더 큰 순서대로 정렬하는 것"!
이제 좀 이해가 됐어? 😊

'프로그래머스 > LV.2' 카테고리의 다른 글

[프로그래머스][LV.2] 더 맵게 \| python3 (0)	2025.03.12
[프로그래머스][LV.2] H-Index \| python3 (0)	2025.03.12
[프로그래머스][LV.2] 프로세스 \| python3 (0)	2025.03.10
[프로그래머스][Lv.2] 의상 \| python3 (0)	2025.03.05
[프로그래머스][LV.2] 전화번호 목록 \| python3 (0)	2025.03.05

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

꾸준히

꾸준히

태그

최근글

댓글

공지사항

아카이브

문제설명

제한조건

문제풀이

나의코드

🔹 첫 번째 풀이: functools.cmp_to_key를 이용한 정렬

🔍 풀이 과정

✅ 핵심 포인트

🔹 두 번째 풀이: 직접 cmp_to_key 구현

🔍 풀이 과정

✅ 핵심 포인트

🔥 두 풀이 비교

🚀 결론

1️⃣ sorted() 함수

2️⃣ cmp_to_key()의 역할

3️⃣ 핵심 코드 분석

🔹 sorted(n, key=functools.cmp_to_key(comparator)) 동작 과정

4️⃣ 실행 예제

🔥 정리

'프로그래머스 > LV.2' 카테고리의 다른 글

관련글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역