[Python] BOJ 4375

📌 처음 풀었던 코드 – 문자열로 구현 (짱오래걸림)

처음에는 단순하게 문자열을 이용해 1, 11, 111, 1111...을 만들어가면서 n으로 나누어떨어지는지 확인하는 방식으로 접근함

import sys

n = int(sys.stdin.readline().strip())

while True:
    next = sys.stdin.readline().strip()

    tmp = '1'

    while int(tmp) % n != 0: 
        tmp += '1'
    print(len(tmp))  

    if not next:
        break
    n = int(next)

 

🔎 왜 오래 걸릴까?

• tmp가 문자열이기 때문에 int(tmp)로 변환할 때 숫자의 자리수(k)에 비례하는 시간 복잡도가 발생함.
• int(tmp) % n 연산을 반복하면서 매번 정수 변환이 일어나므로 전체적으로 O(k^2)의 시간 복잡도가 됨.
• k가 커지면 커질수록 연산량이 급격하게 증가해서 시간 초과 발생

 

📌 두 번째 시도 – 정수 연산으로 변환 (그래도 느림 )

문자열을 직접 변환하는 게 문제라면 정수 연산으로 직접 계산하면 더 빠르지 않을까? 하는 생각
그래서 tmp를 숫자로 두고 10의 제곱수를 더하는 방식으로 변경

while True:
    next = sys.stdin.readline().strip()

    tmp = 1  
    ct = 1 

    while tmp % n != 0:
        tmp += 10 ** ct
        ct += 1
    print(ct)

    if not next:
        break
    n = int(next)

🔎 그래도 느림... 왜?

• 10 ** ct 연산이 반복되면서 큰 숫자를 직접 다루게 됨.
• tmp가 점점 커지면서 Python의 다중 정밀도 정수 연산이 발생하여 속도가 느려짐.
• 결국 큰 수 연산을 직접 다루는 방식이라 비효율적임.
• 시간 복잡도는 O(k)지만, 실제 실행 시간이 오래 걸리는 문제 발생! 🤦‍♂️

 

📌 정답 코드 – 모듈러 연산 활용

while True:
    try:
        n = int(input())
        i = 1
        count = 1

        while True:
            if i % n != 0:
                i = i * 10 + 1
                count += 1
            else:
                print(count)
                break
    except:
        break

🔎 모듈러 연산

• i % n 값만 추적하면 되므로 큰 숫자를 직접 다루지 않아도 됨.
• i = i * 10 + 1 연산을 반복하지만, 항상 n보다 작은 나머지만 유지하면 되기 때문에 속도가 빠름.
• 즉, 나머지만 추적하면서 계산하기 때문에 큰 숫자를 직접 다루지 않고도 정답을 찾을 수 있음.
• 결과적으로 훨씬 빠르게 실행됨!
• n이 7일 때 예시 ↓

i = 1, 1 % 7 = 1
i = 11, 11 % 7 = 4
i = 111, 111 % 7 = 6
i = 1111, 1111 % 7 = 2
i = 11111, 11111 % 7 = 0

 

📌 결론 – 왜 모듈러 연산을 사용해야 할까?

	사용 방법	시간 복잡도	실행 속도
첫 번째 코드	문자열 변환 사용	O(k^2)	1652ms
두 번째 코드	큰 숫자 직접 연산	O(k)	640ms
정답 코드	모듈러 연산 활용	O(k)	140ms

• 처음에는 단순하게 문자열로 구현했다가 시간 초과 발생.
• 그다음 정수 연산을 사용했지만, 큰 숫자를 직접 다뤄서 여전히 느림.
• 결국 모듈러 연산을 활용하여 나머지만 추적하면 훨씬 빠르다는 걸 알게 됨.

📌 모듈러 연산을 활용하면 큰 숫자를 직접 계산하지 않아도 되기 때문에 실행 속도가 확연히 빨라진다!
💡 정수의 나머지 값만 유지하면서 연산하면 성능을 크게 개선할 수 있다!

 

🔗 마무리

💚 이 문제를 풀면서 Python에서 큰 숫자를 다루는 연산이 얼마나 느릴 수 있는지 체감할 수 있었고, 모듈러 연산을 활용하면 큰 수를 직접 다루지 않고도 해결할 수 있다는 점을 배웠다.

💚 비슷한 문제를 만났을 때 "큰 숫자를 직접 계산할 필요가 있을까?" 라고 한 번 더 고민해보면 더 효율적인 풀이를 찾을 수 있을 것 같다!