큰 수에서 나머지 구하는 방법

Bruce Han·2023년 1월 23일

Java 튜토리얼

목록 보기

3/3

백준 14928번 큰 수(BIG)라는 문제는 제연이의 생일(20000303)로 그가 좋아하는 수를 나눈 나머지를 구하는 문제입니다.
큰 수라길래 BigInteger로 mod() 혹은 remainder() 메서드를 이용하면 풀리겠다 생각할 수 있지만, 시간 초과가 나기 때문에 더 효율적인 방법인 나머지 연산 분배 법칙에 대해 알아보고 어떤 차이가 있는지 소스와 결과를 Java언어를 통해 알아보는 포스팅입니다.

문제는 생략하고, 본론부터 얘기하자면

두 방법의 결과

BigInteger를 사용했을 때

시간 초과가 발생한다.

나머지 연산 분배 법칙

통과된다.

무슨 차이가 있는 것일까?

두 방법의 소스 비교

BigInteger의 remainder()

먼저 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을 해주는 것과 같게 된다.

charAt(index) - '0'

예시에서는 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 처럼 되는 것이다.

References

Bruce Han

만 가지 발차기를 한 번씩 연습하는 사람은 두렵지 않다. 내가 두려워 하는 사람은 한 가지 발차기를 만 번씩 연습하는 사람이다. - Bruce Lee

이전 포스트