프로그래머스 - 가장 큰 수 (정렬)

프로그래머스 문제

 

🔸 문제 해결 방향

1. 문자열 처리를 통해 풀어야한다.
2. 문자열 비교가 어떻기 이루어지는지 숙지할 것
   • 문자열 곱셈을 수행한 뒤 비교한 이유는?
3. 문자열 비교 → 숫자 변환 → 문자열 변환 후 반환
   • 숫자로 바꾸어 주지 않을 시 발생하는 문제는?

문제 접근

1. 리스트 정렬 기능 이용하기

처음 시도는 리스트 정렬 기능을 이용했다.

정렬 시 기준이 되는 key 값을 문자열의 첫 번째 값으로 설정했다.

첫째자리수가 가장 클 경우 앞 쪽에 배치된다.

❌ 첫째 자리 수가 같은 경우 발생

1. 5와 50은 어떻게 비교할까? → 정렬 시 2번째 기준을 문자열 길이로 설정한다.
2. 둘째 자리 수가 같을 경우 문자열 길이가 짧은 쪽이 앞에 배치된다.

❌ 그럼 5, 56, 3의 경우는 어떨까? → 정렬 시 2번째 기준

1. 56, 5, 3이 되어야 한다.

처음에 문자를 숫자로 변환한 뒤 비교를 수행하도록 접근했다.

이 경우 문제는 풀이가 너무 복잡해졌다.

2. 문자열 비교 수행

본래 이 문제의 취지는 문자열 비교 규칙을 숙지하고 활용할 수 있느냐였다.

• '5'는 '4'보다 크다.
• '5'는 '444'보다 크다.

⭕ 문자열 그대로를 비교하자.

이를 구현한 코드는 다음과 같다.

소스코드

def solution(numbers):
    """ number를 받아 가장 큰 수를 정렬하는 함수

    Notes:
        1. 핵심은 숫자를 문자열로 반환한 뒤, 문자열 비교를 수행하는 것이다.
        2. 모든 숫자를 문자열로 비교하기 위해 문자열 곱셉을 수행하였다.
        3. 마지막에 0000과 같은 중복값을 제거하기 위해 int로 반환한 뒤 다시 string으로 반환하였다. 

    Args:입력
        numbers (list): int형 숫자를 담은 리스트

    Returns
        정렬한 값들을 string으로 연결한 문자열 반환

    """
    answer=''
    answer = sorted(list(map(str, numbers)), key=lambda x: x*5, reverse=True)

    return str(int(''.join(answer)))

q = [3, 30, 34, 5, 9]
print(solution(q))

다소 의문이었던 점은 왜 문자열 곱셈을 수행한 뒤 비교를 진행하였을까?

❤ 첫번째 문자 같은 경우를 비교하기 위해서이다.

예를 들어,

'5' > '10000000'은 True이다.

→ 첫번째 문자인 5가 1보다 크기 때문이다.

❓ '5'와 '50'은 어떨까?

'5' > '50'은 False이다.

→ 첫번째 문자가 같다면, 자리 수가 더 많은 50이 5보다 크다.

하지만 문제의 조건은 가장 큰 수를 만드는 것이다.

❗ '505'가 아니라 '550'을 만드는 것이 목적이다.

→ 따라서 문자열을 길게 나열하기 위해 * 5를 통해 문자열을 반복했다.

• '3' * 5 = '33333'

💠 '3' * 5 > '30' * 5 는 True이다.

• '33333' > '3030303030'이므로 2번째 자리에서 크기 비교가 끝난다.

💠 또한, 최종문자열을 숫자로 변환한 뒤, 다시 문자열로 변환한다.

• 이유는 '0000'과 같은 예외가 있기 때문이다.
• '0000' → 0 → '0'

참고한 블로그