[Java] 백준 24955 숫자 이어 붙이기 (G4)

문제 해결 전략

숫자를 이어붙이는 문제였다.

처음에는 문제를 잘못 이해해서 각 집에 붙어 있는 수를 반대로도 뒤집을 수 있는 줄 알았는데, 그냥 순차적으로 이어붙이는 문제이다.

BFS를 통해 각 집을 방문한다면 어렵지 않게 이어 붙인 수를 구할 수 있다.

그러나 이 문제의 킥은 그게 아니였다.

집에 붙어 있는 숫자가 1,000,000,000일 수 있기 때문에 long을 사용해도 String → Long에서도 NumberFormatException이 날 수 있다.

그냥 수를 계속 더하는 것이면 Modular의 분배 법칙을 사용할 수 있다.

근데 이 문제는 수를 이어 붙이는 것이다. 이를 위해서는 곱셈에 대한 분배법칙도 사용하여야 한다.

이를 이용하면 두 수를 붙일 때도 모듈러 연산을 할 수 있고 오버플로우를 방지할 수 있다.

 

예를 들어 ) 숫자 a와 b를 합친다고 하면

 로 표현할 수 있고

여기에 각각 모듈러 연산을 넣으면

으로 표현할 수 있다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_24955 {

    private static final long DIVIDE = 1_000_000_007;
    private static int n;
    private static int[] home;
    private static List<Integer>[] map;

    public static void main(String[] args) throws IOException {
        int times;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        times = Integer.parseInt(st.nextToken());
        home = new int[n + 1];
        map = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            map[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            home[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            map[from].add(to);
            map[to].add(from);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < times; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            sb.append(solve(from, to) % DIVIDE).append("\n");
        }
        System.out.println(sb);
    }

    private static long solve(int from, int to) {
        boolean[] visit = new boolean[n + 1];
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(from, home[from]));
        visit[from] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            if (point.current == to) {
                return point.value;
            }

            for (int i : map[point.current]) {
                if (!visit[i]) {
                    visit[i] = true;
                    long result = (((point.value % DIVIDE) * (power(String.valueOf(home[i]).length()) % DIVIDE)) % DIVIDE + home[i] % DIVIDE) % DIVIDE;
                    queue.add(new Point(i, result));
                }
            }
        }
        return 0;
    }

    private static long power(int count) {
        return Long.parseLong("1" + "0".repeat(Math.max(0, count)));
    }

    static class Point {
        int current;
        long value;

        public Point(int current, long value) {
            this.current = current;
            this.value = value;
        }
    }
}

인데 여기서 power 함수를 더 최적화 할 수 있다.

문자열 연산을 사용하게 되면 비효율적이고, 만약 그 값이 크다면(그럴리 없지만) long으로 변환시 오버플로우의 가능성이 있다.

private static long power(int count) {
    long result = 1;
    long base = 10;

    while (count > 0) {
        if ((count & 1) == 1) { // count가 홀수이면
            result = (result * base) % DIVIDE;
        }
        base = (base * base) % DIVIDE; // base를 제곱
        count >>= 1; // count를 2로 나누기 (count /= 2)
    }

    return result;
}

이 함수는 O(log count)의 시간복잡도를 갖는다.

느낀점

이 문제는 그래프의 시각으로 보면 어려운 문제는 아니였지만, overflow를 얼마나 고려하였고 그 실행 시간을 어떻게 하면 줄일 수 있는지 고민해야 하는 문제였다.

정답의 문턱에서 고민을 좀 했다.