백준 그리디 문제입니다.

문제

https://www.acmicpc.net/problem/10610

그리디 문제입니다. 주어진 수에서 숫자를 조합하여 30의 배수를 갖는 최댓값을 구하는 문제였습니다. 빠르게 최댓값을 찾기 위해 내림차순 정렬하는 데까지 도달했지만 모든 경우의 수를 구하기엔 N은 10^5까지 주어지기에 시간초과가 날 것이라고 생각했습니다.🐦🐦🐦

다른 해법이 떠오르지 않아 다른 풀이들을 참고하였고 3의 배수임을 알기 위한 공식을 활용한 풀이를 볼 수 있었습니다.

30의 배수를 구하기 위한 조건으로

1. 10의 배수 : 끝자리가 0이여야 한다
2. 3의 배수 : 모든 자릿수의 합이 3의 배수여야 한다.

을 통해 쉽게 해결할 수 있었습니다.

[나의 풀이]

N = str(input())

ans = -1
nums = list(N)

# 정렬했기 때문에 0이 있다면 이미 맨끝
nums = sorted(nums,reverse=True)

# 30의 배수
# 3의 배수 : 모든 수의 합이 3의 배수
# 10의 배수 : 끝자리가 0
if '0' not in nums:
    print(-1)
else:
    n_sum = 0 
    for i in range(len(nums)):
        n_sum += int(nums[i])

    if n_sum%3 == 0:
        print("".join(nums))
    else:
        print(-1)

[다른 사람의 풀이1]

n = str(input())
nums = list(map(int, n))
if sum(nums) % 3 == 0:
    nums.sort(reverse=True)
    if nums[-1] == 0:
        print(''.join(list(map(str, nums))))
    else:
        print(-1)
else:
    print(-1)

[다른 사람의 풀이2]

n = input()

if "0" not in n:
    print(-1)

else:
    num_sum = 0
    for i in range(len(n)):
        num_sum += int(n[i])

    if num_sum % 3 != 0:
        print(-1)
    
    else:
        sorted_num = sorted(n, reverse=True)
        answer = "".join(sorted_num)
        print(answer)

다른 풀이에서도 30의 배수에 해당하는 두 조건을 활용한 풀이였으며 정렬을 언제하는지에 대한 순서만 달랐습니다.🐤🐤🐤

감사합니다.