[SWEA] Python 14361. 숫자가 같은 배수(D3)

문제 바로가기

접근 방법

1. 재배열한다고 숫자를 바꿔가는 방법을 생각하면 안 된다. 언제나 그렇듯 규칙을 찾는다.
2. 규칙이라 말하기도 애매하지만, 원래의 자릿수보다 자릿수가 늘어나면 비교자체가 불가능하다.
   예로 1035가 있는데 10350이 되면 1035를 아무리 재배열 해봐도 10350을 만들 수 없다.
3. 때문에 원래의 자릿수보다 커지기 전까지만 곱셈을 해야 한다.
4. 1035에 3을 곱한 3105가 그 답이 될텐데 이 둘은 위치는 다르지만 모든 값이 서로에게 포함되어 있다.
5. 정렬을 이용하면 0135로 둘은 동일한 걸 알 수있다.

풀이

T = int(input()) # 테케 입력

for i in range(1, T+1):
    num_str = input() # 숫자 N 입력
    num_list = sorted(list(num_str)) # 입력받은 N 정렬된 리스트로 만들기

    flag = False # 숫자가 같은지 체크
    k = 2 # 배수
    while True:
        multi_num = int(num_str) * k # 2N, 3N ... k*N
        if len(str(multi_num)) > len(num_str): # 만약 원래 길이보다 늘어나면 종료
            break

        if sorted(list(str(multi_num))) == num_list: # 배수와 원래 숫자의 구성이 같으면 종료
            flag = True
            break

        k += 1

    if flag:
        answer = "possible"
    else:
        answer = "impossible"

    print(f"#{i} {answer}")