SW Expert Academy - 1945. 간단한 소인수분해(D2)

출처 - https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5Pl0Q6ANQDFAUq&categoryId=AV5Pl0Q6ANQDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=2

SW Expert Academy

<나의 풀이>

코딩 테스트를 준비한다면 단골로 등장하는 소인수분해이다.

이번에도 테스트 케이스의 수 T가 주어지고,

각 테스트 케이스마다 주어지는 N에 대해서 2, 3, 5, 7,11에 대한 소인수분해를 하는 것이 문제이다.

먼저 입력값 세팅을 하고 시작해보자.

T = int(input())
for i in range(1,T+1):
    N = input()
    print("#{} {}".format(i,N))

소인수분해라는 것이 결국 나누기를 활용하면 좋은데,

예를 들어서 N을 2로 최대한 나눠보고 그 횟수를 카운트 한 것이 2의 a승에 해당한다.

또한 2로 단 한 번이라도 나눠지지 않는다면 그 횟수는 0이 된다.

다행히 문제에서 소수를 주어줬기 때문에 조금 더 빠르게 접근이 가능하다.

a, b, c, d, e 변수에 대해서 선언하고 for문 안에서 새로운 for문을 실행해보자.

intN = int(N)
a, b, c, d, e = 0, 0, 0, 0, 0

이전까지는 리스트 요소에 대해서 제어를 했었지만,

이번 문제에서는 나눗셈을 활용하기 위해 정수형 변수들을 사용해보자.

단순하게 생각했을 때 입력값 N을 2로 나누었을 때 나머지가 0이라면 다시 나눠야 한다.

즉 조건이 들어간 반복문을 사용하기 위해서는 while이 좋아 보인다.

while( intN%2 == 0):
    intN /= 2
    a += 1

입력값 N을 2로 나눈 나머지가 0이라면 2의 배수이므로 N에 2로 나눠준 값을 저장하고 a는 1이 증가한다.

만약 2로 나눈 나머지가 0이 아니라면 반복문은 실행되지 않기 때문에 a 값을 변화시킬 수 없다.

이런 방식으로 코드를 작성해보니 다음과 같다.

T = int(input())
for i in range(1,T+1):
    N = input()
    intN = int(N)
    a, b, c, d, e = 0, 0, 0, 0, 0
    while( intN%2 == 0):
        intN /= 2
        a += 1
    while( intN%3 == 0):
        intN /= 3
        b += 1
    while( intN%5 == 0):
        intN /= 5
        c += 1
    while( intN%7 == 0):
        intN /= 7
        d += 1
    while( intN%11 == 0):
        intN /= 11
        e += 1
    print("#{} {} {} {} {} {}".format(i,a,b,c,d,e))

문제를 풀기는 했으나 상당히 길고 더러운 코드이다.

이렇게 while문이 반복되는 구조를 단순하게 만들어 줄 필요가 있다.

그래서 for문을 활용해보기로 했다.

for j in ?:

내가 원하는 것은 j라는 변수에 2,3,5,7,11을 활용하는 것이다.

따라서 이들이 담긴 리스트 S를 새로 선언해주자.

S = [2,3,5,7,11]
for j in S:

이제 for문 안에서 N을 j로 나누는 조건문을 생성하되, 반복적으로 여러 변수가 들어가야 함을 잊지 말자.

S = [2,3,5,7,11]
for j in S:
    if (intN%j) == 0:
        intN /= j
        ?

여기서 위에서 푼 것처럼 각 a b c d e에 대해서 1씩 증가해주면 좋은데,

이 변수를 어떻게 가지고 올지가 고민이다.

가장 익숙한 카운트 방식은 새로운 리스트를 선언하고 그 안에서 요소에 1을 더해주는 방식이다.

따라서 새로운 리스트 E를 선언하자.

이때 리스트 E의 인덱스를 a b c d e라고 생각하면 좋겠다.

즉 E[2]를 +1 해준다는 것은 즉 a가 1 증가한다고 생각하는 것이다.

따라서 리스트 E는 길이를 12로 해줘야겠다.(0부터 11까지이니깐)

이를 작성하면 다음과 같다.

S = [2,3,5,7,11]
E = [0]*12
for j in S:
    if (intN%j) == 0:
        intN /= j
        E[j] += 1

하지만 여기서 생각하지 않은 것이 있는데, 이는 j로 최대한 나누는 것이 되지 않는다.

그 이유는 조건문 if를 사용했기 때문이다.

이를 while문으로 바꾼 최종 코드는 다음과 같다.

T = int(input())
for i in range(1,T+1):
    N = int(input())
    S = [2,3,5,7,11]
    E = [0]*12
    for j in S:
        while (N%j) == 0:
            N /= j
            E[j] += 1
    print("#{} {} {} {} {} {}".format(i,E[2],E[3],E[5],E[7],E[11]))

아까보다 훨씬 더 깔끔한 느낌이다.

이렇게 코드를 개선하는 작업도 할 줄 알게 되었다니(대단한 문제는 아니었지만...)

더 디테일하게 새로 선언한 리스트 E에 대해서도 더 간략하게 수정할 수 있는 방법이 있을 것 같다.

왜냐하면 2,3,5,7,11 이외의 인덱스는 필요가 없기 때문이다.

이에 대해서는 지금은 찾지 않겠다.