백준 14928번 큰 수(BIG)라는 문제는 제연이의 생일(20000303)로 그가 좋아하는 수를 나눈 나머지를 구하는 문제입니다.
큰 수라길래 BigInteger로 mod() 혹은 remainder() 메서드를 이용하면 풀리겠다 생각할 수 있지만, 시간 초과가 나기 때문에 더 효율적인 방법인 나머지 연산 분배 법칙에 대해 알아보고 어떤 차이가 있는지 소스와 결과를 Java언어를 통해 알아보는 포스팅입니다.
문제는 생략하고, 본론부터 얘기하자면
시간 초과가 발생한다.
통과된다.
무슨 차이가 있는 것일까?
먼저 remainder()를 이용한 소스는 이렇다.
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
BigInteger num = new BigInteger("123456789123456789123456789123456789123456789123456789123456789123456789");
BigInteger birthday = new BigInteger("20000303");
BigInteger remainder = num.remainder(birthday);
System.out.println("나머지 : " + remainder);
}
}
나머지 : 1313652
시작시간(나노초) : 402352000
종료시간(나노초) : 403352700
나노초 차이: 1000700
remainder()에 대한 더 자세한 설명은 오라클 공식문서를 참고하면 된다.
public class Main {
public static void main(String[] args) {
String num = "123456789123456789123456789123456789123456789123456789123456789123456789";
long remainder = 0;
for(int i = 0; i < num.length(); i++) {
remainder = (remainder * 10 + (Character.getNumericValue(num.charAt(i)))) % 20000303;
// Character.getNumericValue(num.charAt(i)) 대신 num.charAt(i) - '0'도 가능;
}
System.out.println("나머지 : " + remainder);
}
}
나머지 : 1313652
시작시간(나노초) : 710508900
종료시간(나노초) : 711340100
나노초 차이: 831200
나머지 연산 방법
이 BigInteger를 통한 나머지 메서드
를 이용한 것보다 약 20만 나노초 빠르다는 것을 알 수 있다.
(A+B)%M == ((A%M) + (B%M))%M
위 소스는 분배법칙에서 덧셈에 대해 다음과 같음을 보여주는 식이다.(M은 나누는 수)
그러면, 예를 들어 N = abcde
라고 할 때 N = abcde = a10000 + b1000 + c100 + d10 + e*1 이라고 할 수 있다.
a*10000을 a0000라고 표현하면, abcde % mod는 분배법칙에 따라 (a0000%mod + b1000%mod + c100%mod + d10%mod + e%mod)%mod 가 된다.
따라서, remainder라는 변수에 최종 출력할 답을 구한다고 하면, N을 큰 자리수부터 쭉 보면서 다음의 로직을 수행하면 된다. 그러면 remainder는 int 타입으로도 충분히 연산이 가능해진다.
1. for(int i = 0; i < num.length(); i++)
- 입력 자릿수만큼 반복
2. remainder *= 10
- remainder의 10만큼 곱함
3. remainder += (num.charAt(i) - '0')
- remainder에 i번째 자릿수를 더함
4. remainder %= 20000303
- remainder를 20000303으로 나눈 나머지를 구함
여기서 2번 과정은 큰 수 연산을 하지 않기 위해 사용된 부분이다. 즉, 위의 로직대로 하려면 N의 가장 왼쪽 수에 대해 a1000000...000000을 해줘야 하는데, 큰 수라는 것이 결국 수를 String으로 표현하는 방식이므로 이미 여기서 자릿수만큼 시간복잡도가 발생하게 되므로 느려질 수밖에 없다. 따라서 2번 과정에서 이전에 구한 값을 매번 병렬적으로 10을 하면 a*1000000...000000을 해주는 것과 같게 된다.
예시에서는 Character.getNumericValue(객체.charAt(index))처럼 클래스를 통하여 숫자로 바꾸는 메서드를 이용했지만, String타입객체.charAt(int index) - '0'를 이용해도 결과는 비슷하다.
String타입객체.charAt(int index) - '0'은 문자를 숫자로 바꿀 때 자주 쓰이는 방법 중 하나다.
예를 들어 '1'을 숫자로 바꾸고 싶다면 '1' 자체는 아스키코드 값으로 49이기 때문에, 아스키 값이 48인 '0'을 빼면 자연스레 int형 1이 나오게 된다. '2'는 아스키 값이 50이니까 '2' - '0' == 2 처럼 되는 것이다.