SWEA 10965번 D3 제곱수 만들기 파이썬

리뷰

D3 첫 도전, D3는 적당히 풀 수 있을 것 같아 가장 정답률이 낮은 문제를 택했다. 정답률 13%로 어떤 문제길래 이렇지? 하고 풀어보니 시간초과 파티였다. 딕셔너리를 통해 문제를 풀어 겨우 통과하였다.

문제 풀이

1. 각 케이스 마다 빈 딕셔너리를 하나 초기화 해준다.
2. 현재 수를 소인수 분해 해주고 각 소인수의 지수를 딕셔너리의 value 값으로 추가 해준다.
3. 마지막 인자가 소수일 경우 이 또한 딕셔너리에 추가해 준다.
4. 거듭 제곱수를 구하는 문제지만 결국 제곱수가 b의 최소값이므로 딕셔너리의 value값이 홀수일 경우 key값을 b에 곱해준다. (소인수한 모든 지수를 짝수로 맞춰주면 해당 값이 거듭제곱 값이 되는 최소값이다.)
5. 각 케이스의 정답을 result 리스트에 추가해 주고 마지막에 result 리스트의 인자를 모두 출력해 준다.

참고 사항

각 케이스마다 print를 해줄 경우 시간이 많이 잡아먹는다고 한다. 정답을 저장해 두었다가 한번에 출력하도록 하자.

정답 코드

def q10965():
    # SWEA 10965번 D3 제곱수 만들기 파이썬
    t = int(input())
    result = []
    for i in range(1, t + 1):
        a = int(input())
        dic = {}

        k = 2
        while k ** 2 <= a:
            while a % k == 0:
                if k in dic:
                    dic[k] += 1
                else:
                    dic[k] = 1
                a //= k
            k += 1
        if a > 1:
            dic[a] = 1
        b = 1
        for key, val in dic.items():
            if val % 2:
                b *= key
        result.append(f'#{i} {b}')
    for i in result:
        print(i)
q10965()