백준 10610. 30 (Python/파이썬) (순열, 조합, 시간초과 해결)

🔎 10610번. 문제 보기
https://www.acmicpc.net/problem/10610

💡 문제 풀기 전
처음 문제 접근할 때 생각했던 알고리즘은

1)
입력 받은 수에서 0이 1개 이상 있는지 체크하고

2)
있다면 리스트를 내림차순으로 정렬하여 0을 pop으로 빼준 다음
남은 리스트 요소들로 정렬할 수 있는 모든 경우의 수를 만들어줘야지

3)
경우의 수를 만들고 나면, 그 수들 중에서 3으로 나눠 떨어지는 것을 체크하자
거기서 가장 큰 수를 뒤에 0을 붙여서 출력하면 되겠다!


였는데.. 이대로 구현해보니 답은 나왔지만 시간초과가 떠버렸다.

📋 코드 보기

1) 1차 시도 - 시간초과

from itertools import permutations
from sys import stdin

N = list(stdin.readline().rstrip())
N.sort(reverse=True)
if '0' == N[len(N)-1]:
    N.pop()
    test = list(map(''.join, permutations(N)))

    for i in range(len(test)):
        if int(test[i]) % 3 == 0:
            print(test[i]+'0')
            exit()
else:
    print(-1)

2) 2차 시도 - 성공

from sys import stdin

N = list(stdin.readline().rstrip())
N.sort(reverse=True)

print(-1) if N[len(N)-1] != '0' or sum(map(int, N)) % 3 != 0 else print(''.join(N))

🥕 코드 풀이 및 관련 개념

1. 문제풀이 아이디어 (2차 시도 관련)

사실 1차 시도에서도 시간 단축을 위한 꽤 많은 노력을 했지만..
아무래도 모든 경우의 수를 만들고자 했던 것이 시간초과의 원인이지 않았나 싶었다.

근데 그러지 않고서야 3의 배수, 즉 30의 배수인걸 어떻게 알지..?
(라는 의문에 굉장히 고민에 고민을 했다.)

그러다 다른 사람의 풀이를 살짝 보면서 얻은 아이디어.
각 자리 수를 모두 더했을 때 3의 배수이면, 그 수는 3의 배수

print(-1) if N[len(N)-1] != '0' or sum(map(int, N)) % 3 != 0 else print(''.join(N))

그래서 찾아낸 코드가 위 코드인데 가독성이 살짝 떨어지니
다시 풀어서 보면

if N[len(N)-1] != '0' or sum(map(int, N)) % 3 != 0:
    print(-1) 
else:
    print(''.join(N))

처음에 수를 입력받고 나서 내림차순으로 정렬했기 때문에
N이 30의 배수라면 무조건 정렬되어 있는 수가 가장 큰 30의 배수에 해당한다.

그리고 3의 배수가 아니라 30의 배수를 찾아야 하므로
N의 끝자리 수(= N[len(N)-1])가 0임과 동시에
N 각 자리의 수 합(sum(map(int, N)))이 3의 배수여야 한다.

그렇지 않다면 -1을 출력해주고,
맞다면 리스트형이기 때문에 join을 활용해서 출력해주면 된다.

2. 순열(permutations)과 조합(combinations) (1차 시도 中)

처음에 활용했던 순열에 대해 잠깐 언급하고 넘어가보자면,

순열 (permutations)

1. 길이가 n개인 객체 중에서 중복을 허용하지 않고 r개를 뽑아서 나열한다.

2. 같은 값이 뽑혔을 때, 뽑힌 순서가 다르면 경우의 수를 다르게 취급한다.

3. 사용법 : permutations(반복 가능한 객체, r)

from itertools import permutations

n = ['A', 'B', 'C', 'D']

print(list(map(''.join, permutations(n, 2))))

# 결과
>> ['AB', 'AC', 'AD', 'BA', 'BC', 'BD', 'CA', 'CB', 'CD', 'DA', 'DB', 'DC']

조합 (combinations)

1. 길이가 n개인 객체 중에서 중복을 허용하지 않고 r개를 뽑는다.

2. 같은 값이 뽑혔을 때, 어떤 것을 뽑는지만 보기 때문에 뽑힌 순서가 다르다고 해서 다른 경우의 수로 출력되지 않는다.

3. 사용법 : combinations(반복 가능한 객체, r)

from itertools import combinations

n = ['A', 'B', 'C', 'D']

print(list(map(''.join, combinations(n, 2))))

# 결과
>> ['AB', 'AC', 'AD', 'BC', 'BD', 'CD']