백준 2138번 - 전구와 스위치

문제

백준 2138번 - 전구와 스위치

아이디어

• 처음에는 BFS로 각 전구를 켜고 끄고 모든 경우의 수를 확인해보는 방법을 생각했는데 이 경우 모든 전구에 대해 두 가지 경우의 수를 살펴봐야 해서 최악의 경우 O(2^N)이 된다.
• 따라서 O(N)의 방법이 필요한데, 그리디 알고리즘을 적용할 수 있다.
• 그리디로 첫번째 전구부터 초기 전구 상태와 목표 전구 상태의 각 위치를 비교하면서 서로 다르면 켜거나 끈다. 하지만 이때 전구의 상태 변화는 N-1, N+1번째 전구에도 영향을 주게 된다.
• 따라서 2번째 전구부터 이전 번째 전구의 상태를 비교하여 다르면 현재 위치의 전구 상태를 변화시켜 이전 번째 전구의 상태를 맞춰나가는 방식으로 진행한다.
• 2번째 전구부터 비교하기 때문에 첫번째 전구를 눌렀을 때와 누르지 않았을 때 중 최솟값을 찾아야 한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

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

public class BJ_2138 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        boolean[] init = new boolean[n];
        boolean[] target = new boolean[n];

        String s = br.readLine();
        for (int i = 0; i < n; i++) {
            init[i] = s.charAt(i) == '1';
        }

        s = br.readLine();
        for (int i = 0; i < n; i++) {
            target[i] = s.charAt(i) == '1';
        }

        int firstOff = solve(init, target, n, false); //첫번째 전구를 누르지 않은 경우
        int firstOn = solve(init, target, n, true); //첫번째 전구를 누른 경우

        int result = Math.min(firstOff, firstOn);

        System.out.println(result == Integer.MAX_VALUE ? -1 : result);
    }

    private static int solve(boolean[] init, boolean[] target, int n, boolean first) {

        int count = 0; //전구를 누른 횟수
        boolean[] lights = init.clone();

        if (first) {
            toggle(lights, n, 0);
            count++;
        }

        for (int i = 1; i < n; i++) { //2번째 전구부터 이전 번째 전구 비교
            if (lights[i - 1] != target[i - 1]) {
                toggle(lights, n, i);
                count++;
            }
        }

        if (!Arrays.equals(lights, target)) {
            return Integer.MAX_VALUE;
        }

        return count;
    }

    private static void toggle(boolean[] lights, int n, int idx) {
        lights[idx] = !lights[idx];

        if (idx > 0) {
            lights[idx - 1] = !lights[idx - 1];
        }
        if (idx < n - 1) {
            lights[idx + 1] = !lights[idx + 1];
        }
    }
}