[SWEA / D3] 14361. 숫자가 같은 배수 - 파이썬(Python)

문제 링크

SWEA 14361. 숫자가 같은 배수

SW Expert Academy

 

문제

자연수 N이 주어질 때, N의 10진법 표기에서 나타나는 숫자들을 재배열하여 N보다 큰 배수(2N, 3N, 4N ... kN)를 만들 수 있는지 여부를 판단하는 코드를 작성하는 문제입니다. 단 N은 0으로 시작하지 않도록 표기해야 합니다.

 

입력

첫 번째 줄에 테스트 케이스 T가 주어지고, 테스트 케이스는 각 줄마다 자연수 N(1 <= N <= 10^6)이 주어집니다.

 

출력

주어진 N의 숫자를 재배열하여 더 큰 배수를 만들 수 있다면 'possible', 없다면 'impossible'를 출력합니다.

 

 

입출력 예

입력

3
142857
1
1035

 

출력

#1 possible
#2 impossible
#3 possible

 

문제 풀이 및 코드

문제를 접근할 때, itertools 라이브러리의 permutations 함수를 이용하여 재배열의 모든 경우의 수를 구하여 조건에 맞추어 풀이하는 방법을 떠올렸습니다. permutations 함수는 순열과 조합에서 순서를 중요시하는 순열입니다.

 

순열을 이용한 경우의 수 구하기

import itertools
 
nums = [1, 2, 3, 4]
 
for i in itertools.permutations(nums, 3):
    print(i)

배열 permutations 함수를 통해 경우의 수를 구하는 예시입니다. nums 배열 [1, 2, 3, 4]에서 3가지를 뽑아 구하는 코드로

i는 [1, 2, 3], [1, 3, 2], [1, 2, 4], [1, 4, 2] ... 등 모든 경우의 수를 출력하게 됩니다.

만약, 중복된 수를 뽑지 않길 원한다면 순서를 신경 쓰지 않는 itertools 라이브러리의 combinations 함수가 존재합니다.

 

문제풀이

먼저, 만약 입력값 자연수 N이 길이가 1인 자연수라면 재배열을 할 수 없으며 더 큰 배수를 찾을 수 없습니다.

따라서 len(n)이 1인 경우 impossible를 출력하도록 합니다. 이후 다음 테스트 케이스를 판별하기 위해 continue를 사용하였습니다.

 

len(n)이 1이 아닐 경우 순열을 사용하여 더 큰 배수 찾기를 진행합니다.

temp 문자열을 이용하여 임시적으로 순열의 i 값을 담기 위해 초기화한 후 i 값을 담은 뒤 num_list 리스트에 추가하여 담았습니다.

temp[0] 값이 만약 0이라면 올바른 값이 아니기 때문에 굳이 판별할 필요가 없어 num_list에 담지 않았습니다.

 

순열의 반복문이 끝이 나면 num_list에는 길이가 1이 아닌 자연수 n의 재배열된 값 중 첫 수가 0이 아닌 모든 경우의 수가 담겨 있습니다.

이제 num_list안에 n보다 더 큰 배수가 존재한다면 possible, 아니면 impossible를 출력해야 합니다.

 

이를 판단하기 위해 반복문을 통해 num_list에 존재하는 값을 n으로 나누었을 경우 나머지가 0이 되는지를 판별합니다.

check 변수를 통해 존재 여부를 체크한 뒤 더 큰 배수가 존재하면 possible, 아니면 impossible를 출력하도록 합니다.

 

ㅈ코드

from itertools import permutations
 
t = int(input())
 
for tc in range(1, t+1):
    n = input()
    num = int(n)
    length = len(n)
    num_list = []
    check = 0
 
    if len(n) == 1:
        print('#%d impossible' % tc)
        continue
 
    for i in permutations(n, length):
        temp = ''
        for j in i:
            temp += j
        if temp[0] != '0':
            if int(temp) not in num_list:
                num_list.append(int(temp))
 
    for i in range(1, len(num_list)):
        if num_list[i] % num_list[0] == 0:
            check = 1
 
    if check == 1:
        print('#%d possible' % tc)
    else:
        print('#%d impossible' % tc)

본 코드는 제가 직접 작성한 것으로 더 나은 코드가 존재할 수 있으니 참고하시기 바랍니다.