BOJ2609-최대공약수와 최소공배수 (python3)

자꾸 시간초과 떠서 3트 만에 성공...

유클리드 호제법..?
그게 뭔데~

이곳에서 유클리드 호제법을 배웠어요~!

아니 이거 어떻게 아시는거임?
나도 지나가다 들어보긴 한 것 같은데 이거 어떻게 생각하냐 진짜로....

코드 엄청 길었는데 확 줄어들었다.

이 코드에는 sort 개념도 있어야되고, swap 개념도 있어야되지만, 뭐니뭐니 해도 유클리드 호제법 모르면 다소 길이가 많이 길어지고 시간이 좀 걸리는 문제인 것 같다.

maxnum, minnum = 0,0
n_list= list(map(int,input().split()))
n1, n2 = n_list[0], n_list[1]
n_list.sort()
while True:
    if n_list[1]%n_list[0] != 0:
        tmp = n_list[0]
        n_list[0] = n_list[1]%n_list[0]
        n_list[1] = tmp
        n_list.sort()
    else:
        minnum = n_list[0]
        break
print(minnum, n1*n2//minnum)

내가 시간 초과로 애먹었던 코드는 바로 다음과 같다.
카운팅 정렬이라는 해괴망측(?)한 방법을 사용한게 1안이었고,

n1, n2 = map(int,input().split())
origin_n1, origin_n2 = n1,n2
n1_list = [0]*10001
n2_list = [0]*10001
i,j = 2,2

while True:
    if n1%i == 0:
        n1_list[i] += 1
        n1 //= i
    elif n1 // i != 1:
        i += 1

    if n2%j == 0:
        n2_list[j] += 1
        n2 //= j
    elif n2 // j != 1:
        j += 1

    if n1//i == 1 and n2 // j ==1:
        n1_list[n1] += 1
        n2_list[n2] += 1
        break

nn_list = []

for idx, val in enumerate(n1_list):
    if val != 0 and n2_list[idx] != 0:
        nn_list.append(idx)

maxnum, minnum = 1, 1
if nn_list!=[]:
    for i in nn_list:
        maxnum *= i**min(n1_list[i],n2_list[i])
        minnum *= i**max(n1_list[i],n2_list[i])
    print(maxnum, minnum)
else:
    print(1, origin_n1*origin_n2)

2안은

n1, n2 = map(int,input().split())
n1_list, n2_list = [],[]
i,j,maxnum,minnum,origin_n1,origin_n2=2,2,1,1,n1,n2
while True:
    if n1%i == 0:
        n1_list.append(i)
        n1 //= i
    elif n1 // i != 1:
        i += 1

    if n2%j == 0:
        n2_list.append(j)
        n2 //= j
    elif n2 // j != 1:
        j += 1

    if n1//i == 1 and n2 // j ==1:
        n1_list.append(n1)
        n2_list.append(n2)
        break
for k in set(n1_list):
    if n1_list.count(k)*n2_list.count(k) != 0:
        maxnum *= k**min(n1_list.count(k),n2_list.count(k))
        minnum *= k**max(n1_list.count(k),n2_list.count(k))
if maxnum*minnum ==1 :
    print(1, origin_n1*origin_n2)
else: print(maxnum, minnum)

개념은 거의 1안과 비슷하지만 카운팅 정렬을 쓰지 않고 리스트를 필요할때마다 재할당해버리는 풀이....
그래도 길이가 줄어들었고, for문이 돌아가는 속도가 비교적 작아진 것 같다고 혼자 최면을 걸어본다. 결국 9999와 10 같은 극단적인 상황에서의 비효율 정도는 똑같겠지만....

하..드디어 집에 간당~
유후 오늘도 수고한 내 자신.기특혀 뽀뽀 쪽쪽쓰