[그리디] 코딩테스트 문제 TIL (30) - 백준 10610번

1. 오늘의 학습 키워드

• Greedy

---

2. 문제: 10610. 30

• 단계: 🥈실버 4단계
• 알고리즘 분류:
  • 수학
  • 그리디 알고리즘
  • 문자열
  • 정렬
  • 정수론
• 출처: https://www.acmicpc.net/problem/10610

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

예제 입력 1 복사

30

예제 출력 1 복사

30

예제 입력 2 복사

102

예제 출력 2 복사

210

예제 입력 3 복사

2931

예제 출력 3 복사

-1

예제 입력 4 복사

80875542

예제 출력 4 복사

88755420

---

3. 문제 풀이

Step1. 문제 이해하기

N이 주어졌을 때, N을 구성하는 숫자들을 조합해서 30의 배수가 되는 가장 큰 수를 반환하는 문제입니다.

이번 문제는 30의 배수 특징만 파악한다면 빠르게 해결이 가능할 것으로 보입니다. 우선, 입출력 조건을 살펴보겠습니다.

• Input:
  • N은 최대 $10^5$개의 숫자로 구성되어 있으며, 0으로 시작하지 않습니다.
    • 이 N은 한 자리 수도 될 수 있지만 0초과라는 것을 알 수 있습니다. 또한 이것이 시간 복잡도에 영향을 줄 것으로 보이기 때문에 $O(n^2)$보다 효율적인 시간 복잡도로 구성해야 합니다.
• Output:
  • 30의 배수가 되는 가장 큰 수를 반환할 수 있다면 그 수를 반환하고, 존재하지 않는다면 -1을 반환합니다.

바로 문제를 분석하러 가보겠습니다.

Step2. 문제 분석하기 및 코드 설계

이번 문제의 핵심은 30의 배수의 특징을 파악하고 이를 활용하여 최적의 해결책을 도출하는 것입니다. 문제를 효율적으로 해결하기 위해 다음과 같은 접근 방법을 사용할 수 있습니다.

30의 배수의 특징

1. 0이 포함되어야 함:
   • 30은 10의 배수이므로 숫자 N에 반드시 '0'이 포함되어야 30의 배수를 만들 수 있습니다.
   • 따라서, N에 '0'이 없다면 바로 1을 반환하면 됩니다.
2. 모든 자릿수의 합이 3의 배수여야 함:
   • 30의 배수는 3의 배수이기도 합니다.
   • 숫자 N의 모든 자릿수 합이 3의 배수가 아니면 30의 배수를 만들 수 없으므로 1을 반환합니다.
3. 가장 큰 30의 배수를 찾아야 함:
   • 가능한 30의 배수 중 가장 큰 값을 구하려면, 숫자들을 내림차순으로 정렬한 값이 답이 됩니다.
   • 예를 들어, 102를 내림차순 정렬하면 210, 80875542를 내림차순 정렬하면 88755420이 됩니다.

알고리즘 설계

위 특징을 기반으로, 문제를 해결하는 과정을 단계별로 나누어 설계합니다:

1. 숫자 N에 '0'이 포함되어 있는지 확인:
   • '0'이 없다면 바로 1을 반환합니다.
   • 이는 30의 배수가 되기 위한 필수 조건입니다.
2. 숫자 N의 자릿수 합이 3의 배수인지 확인:
   • 자릿수 합이 3의 배수가 아니라면 1을 반환합니다.
   • 이는 30의 배수가 되기 위한 두 번째 필수 조건입니다.
3. 숫자 N을 내림차순으로 정렬:
   • 자릿수를 내림차순으로 정렬하면 가장 큰 숫자를 만들 수 있습니다.
4. 결과 출력:
   • 위 조건을 모두 만족하면, 내림차순으로 정렬된 숫자를 하나의 문자열로 반환합니다.

그리디 알고리즘으로 해결

이 문제는 그리디 알고리즘으로 해결할 수 있습니다. 그리디 알고리즘은 "매 순간 최적의 선택을 하여 문제를 해결하는 방법"입니다.

• 조건 확인:
  • 가장 먼저 '0'이 포함되어 있는지 확인하고, 포함되어 있지 않다면 즉시 -1을 반환합니다. 이는 문제를 간단히 처리할 수 있는 최적의 선택입니다.
• 숫자 정렬:
  • 조건을 만족하는 경우, 숫자를 내림차순으로 정렬하여 가장 큰 값을 만듭니다. 이는 가장 큰 숫자를 만들기 위한 최적의 선택입니다.

따라서, 이 문제는 그리디 알고리즘의 특성을 잘 활용한 문제라고 볼 수 있습니다.

코드 설계까지 문제를 제대로 분석한다면 쉽게 이뤄질 수 있습니다. 이제 코드를 보도록 하겠습니다.

Step3. 코드 구현

import sys

N = sys.stdin.readline().strip()

def sol(N):
    num_sum = 0
    if '0' not in N:
        return -1
    
    for i in N:
        num_sum += int(i)
    
    if num_sum % 3 != 0:
        return -1
    return ''.join(sorted(N,reverse=True))

print(sol(N=N))

코드 설명:

1. 입력 값 처리:
   • 입력으로 주어진 숫자 N을 문자열로 받아옵니다. 문자열로 처리하면 각 자릿수를 쉽게 접근할 수 있고, 정렬 작업도 간단히 수행할 수 있습니다.
2. '0' 포함 여부 확인:
   • 숫자 N에 '0'이 포함되지 않으면 30의 배수를 만들 수 없습니다. 따라서 '0' not in N 조건을 통해 False인 경우 바로 1을 반환합니다.
3. 자릿수 합 계산:
   • 모든 자릿수의 합을 계산하여 3의 배수 여부를 확인합니다. 이때, 자릿수 합이 3으로 나누어떨어지지 않으면 30의 배수를 만들 수 없으므로 1을 반환합니다.
4. 내림차순 정렬:
   • sorted(N, reverse=True)를 사용하여 숫자를 내림차순으로 정렬합니다.
   • 정렬된 숫자를 ''.join()으로 연결하여 가장 큰 30의 배수를 만듭니다.
5. 결과 반환:
   • 위 두 조건을 만족하면 내림차순으로 정렬된 값을 문자열로 반환합니다.

시간 복잡도:

1. '0' 포함 여부 확인:
   • '0' not in N은 문자열 N의 길이만큼 확인하므로 $O(n)$입니다.
2. 자릿수 합 계산:
   • 각 자릿수를 순회하며 합산하므로 $O(n)$입니다.
3. 내림차순 정렬:
   • Python의 sorted 함수는 $O(n \log n)$입니다.

따라서, 전체 시간 복잡도는 $O(n \log n)$입니다.

결과:

---

4. 마무리

이 문제는 30의 배수 조건을 활용하여 문제를 간단히 해결할 수 있는 그리디 알고리즘 문제입니다. 중요한 점은 조건을 만족하는지 확인한 후, 내림차순 정렬을 통해 가장 큰 값을 만드는 것입니다.

• 학습 포인트:
  • 숫자에서 특정 조건 확인(0 포함 여부, 자릿수 합 계산).
  • 문자열 정렬을 통한 간단한 그리디 접근.
• 시간 복잡도: $O(n \log n)$으로 효율적이며, 입력 크기 $n$이 최대 $10^5$까지 주어져도 빠르게 실행됩니다.

이번 문제를 통해 조건을 활용한 문제 단순화와 정렬을 활용한 그리디 접근법을 연습할 수 있었습니다!

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!