[백준 15662] 톱니바퀴 (2) - JAVA

문제 링크: https://www.acmicpc.net/problem/15662

접근 방법

이전 톱니바퀴 문제의 확장 버전입니다.
이전 문제에서는 4개의 톱니로 고정였지만
해당 문제에서는 톱니의 개수가 $T$개로 주어지는 문제입니다.
따라서 이전 문제의 핵심 로직은 달라지지 않습니다.

단순히 이전문제를 푸는 것은 의미가 없기 때문에
이전 문제에서 최적화를 하지 못해 아쉬웠던 부분을 최적화해서 구현해보겠습니다.

[Algorithm] 톱니바퀴 연쇄 회전 로직: BFS에서 선형 탐색으로 최적화하기

다른 메서드는 최적화가 되어있기 때문에
회전할 톱니바퀴를 찾는 findRotateCogwheels 로직을 최적화하기로 했습니다.

이전 로직

이전에 회전할 톱니바퀴를 찾을 때 BFS 방식을 사용해
톱니의 회전을 시작할 첫 지점에서부터 BFS를 수행해 가능

개선된 로직

톱니 회전의 첫 지점인 base로부터 왼쪽, 오른쪽으로 선형 탐색

왜 BFS보다 선형 탐색을 사용했나요?

해당 톱니바퀴 문제는 독특한 매커니즘이 있습니다.
회전 한 번 수행할 때
시작 전에 톱니를 모두 스캔해서 가능한 톱니만 회전하는 매커니즘이었기 때문입니다.

그래서 회전 이전에 변화없는 톱니들을 선형으로 탐색할 수 있었고
기존 BFS 방식의 불필요한 메모리 연산을 제거해
메모리 사용량을 줄이고 실행 속도를 향상시켰습니다

코드

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


public class Main {
    static StringTokenizer st;
    static int start = 0;
    static int T;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        int[] cogwheels = new int[T];

        for (int i = 0; i < T; i++) {
            cogwheels[i] = parseDecimal(br.readLine());
        }

        int K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());
            rotateCogwheels(cogwheels, findRotateCogwheels(cogwheels, number, dir));
        }

        System.out.println(getCount(cogwheels));
    }

    static int getCount(int[] cogwheels) {
        int count = 0;
        for (int i = 0; i < T; i++) {
            if ((cogwheels[i] & 1) != 0) {
                count++;
            }
        }
        return count;
    }

    static void rotateCogwheels(int[] cogwheels, int[] isRotate) {
        for (int i = start; i < T; i++) {
            if (isRotate[i] == 0) break;

            int tmp = cogwheels[i];

            if (isRotate[i] == 1) {
                tmp <<= 1;
                if (((tmp & 256) != 0)) {
                    tmp -= 255;
                }
            }
            else {
                if (((tmp & 1) != 0)) {
                    tmp += 256;
                }
                tmp >>= 1;
            }

            cogwheels[i] = tmp;
        }
    }

    static int[] findRotateCogwheels(int[] cogwheels, int number, int dir) {
        int base = number;

        int[] isRotate = new int[T];
        isRotate[base] = dir;

        start = 0;

        while (--base >= 0) {
            if ((((cogwheels[base] & 4) != 0) ^ ((cogwheels[base+1] & 64) != 0))) {
                isRotate[base] = isRotate[base+1] == 1 ? -1 : 1;
            } else {
                start = base + 1;
                break;
            }
        }

        if (start < 0) start = 0;
        base = number;

        while (++base < T) {
            if ((((cogwheels[base] & 64) != 0) ^ ((cogwheels[base-1] & 4) != 0))) {
                isRotate[base] = isRotate[base-1] == 1 ? -1 : 1;
            } else {
                break;
            }
        }

        return isRotate;
    }

    static int parseDecimal(String s) {
        int decimal = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '1') {
                decimal += 1;
            }

            if (i != 0) decimal <<= 1;
        }

        return decimal;
    }
}