SWEA - 간단한 소인수분해(1945)

SW Expert Academy

 

 

문제

N=2a x 3b x 5c x 7d x 11e

N이 주어질 때 a, b, c, d, e 를 출력하라

 

 

접근방식

배열 num_arr = [11, 7, 5, 3, 2] 생성

배열의 각 값들이 몇 번 들어가는지 확인할 배열 ans_arr = [0, 0, 0, 0, 0] 생성

N이 주어지면 num_arr를 순회하면서 N을 각 값들로 나눴을 때 나머지가 0인지 확인

나머지가 0이 아니면 N을 구하는 데 사용되는 숫자가 아니므로 값을 0으로 설정

나머지가 0이면 while True를 통해 나머지가 0이 아닐 때 까지 ans_arr[i]에 1을 더해주고 N을 num_arr[i]로 나눔

 

예로, N이 8575이면 먼저 8575 % 11 = 6으로 0이 아니므로 ans_arr[0] = 0이 되고

8575 % 7 = 0이므로 ans_arr[1] = 1이 되고 N은 N / num_arr[i]에 의해 8575 / 7 = 1225가 됨

다시 1225 % 7 = 0이므로 ans_arr[1] = 2가 되고 N은 1225 / 7 = 175가 됨

175 % 7 = 0이므로 ans_arr[1] = 3이 되고 N은 175 / 7 = 25가 됨

25 % 7 = 4이므로 해당 while문은 break됨

i = 2이므로 num_arr[2] = 5가 되고 25 % 5 = 0이므로 ans_arr[2] = 1, N = 25 / 5 = 5가 됨

5 % 5 = 0이므로 ans_arr[2] = 2, N = 5 / 5 = 1이 됨

i = 3이 되고 num_arr[3] = 3, 1 % 3 = 1이므로 ans_arr[3] = 0

i = 4가 되고 num_arr[4] = 2, 1 % 2 = 1이므로 ans_arr[4] = 0이 됨

 

ans_arr = [0, 3, 2, 0, 0]이 됨

따라서 해당 값을  print('#'+str(n), *(ans_arr[::-1]))를 통해 출력

 

마지막의 ans_arr = [0,0,0,0,0]으로 초기화해주는 이유는 테스트 케이스가 여러개이므로 하나를 수행할 때마다 ans_arr를 초기화해주기 위함

 

-> 생각해보니 for문 안에서 ans_arr = [0,0,0,0,0]으로 설정해주면 굳이 ans_arr를 마지막에서 초기화해줄 필요가 없음. 따라서 for문안에 ans_arr 선언

 

 

코드

#import sys
#sys.stdin = open("input.txt", "r")

T = int(input())
num_arr = [11, 7, 5, 3, 2]
for n in range(1, T + 1):
    ans = 0
    ans_arr = [0,0,0,0,0]
    N = int(input())
    for i in range(len(num_arr)):
        if (N % num_arr[i] != 0):
            ans_arr[i] = 0 
        else:
            while True:
                ans_arr[i] += 1
                N = N / num_arr[i]
                if not (N % num_arr[i] == 0): break
    print('#'+str(n), *(ans_arr[::-1]))