[Algorithm] 백준 - 4375번 1 (Swift)

문제 소개

정말 정말 간단한 문제라서 10분도 안 걸릴 줄 알았지만 생각보다 시간을 쓴 문제... 너무 어려운 거에만 집중하지 말고 이런 단순한 문제에도 집중해야 한다는 것을 깨달았다.
 

문제 풀이

정답 코드는 아래와 같이 단순하다.

while let n = readLine(), let div = Int(n) {
    var num = 1, count = 1
    while num % div != 0 {
        num = (num * 10 + 1) % div
        count += 1
    }
    print(count)
}

 

입력값

여러개의 테스트 케이스로 이루어져 있기 때문에 while을 통해서 readLine()을 사용해 입력값을 계속 받도록 해야 했다.

while let n = readLine(), let div = Int(n) { 
	...
}

 

런타임 에러

아래와 같이 코드를 짜게 되면 num이 점점 커지면서 입력값 div에 따라 Int.max인 9,223,372,036,854,775,807의 범위를 넘을 가능성이 있다.

while let n = readLine(), let div = Int(n) {
    var num = 1, count = 1
    while num % div != 0 {
        num = (num * 10 + 1)
        count += 1
    }
    print(count)
}

 
따라서 아래같이 num을 계속 div로 나눠주면 된다.

while let n = readLine(), let div = Int(n) {
    var num = 1, count = 1
    while num % div != 0 {
        num = (num * 10 + 1) % div
        count += 1
    }
    print(count)
}

 
모듈러 연산의 공식은 아래와 같이 분배법칙이 성립하기 때문이다.

(a + b) mod n = (a mod n + b mod n) mod n
(a * b) mod n = (a mod n * b mod n) mod n

 
아주 간단한 코드였지만 의외로 생각을 꽤 해야 하는 문제였다.