[백준 JAVA] 2138 전구와 스위치

2138 전구와 스위치

https://www.acmicpc.net/problem/2138

문제설명

각 스위치를 누르면 해당 스위치와 인접한 스위치(왼쪽, 오른쪽)가 모두 바뀐다.

주어진 두 가지 초기 상태(첫 번째 스위치 누름 여부에 따라)에서 각각의 경우에 대해

전구의 상태를 변경하여 목표 상태로 만드는 데 필요한 최소한의 스위치 누름 횟수를 구한다.

문제풀이

1. 첫 번째 스위치를 눌렀을 때
2. 첫 번째 스위치를 누르지 않았을 때
3. 각 경우에 대해 스위치를 차례로 확인하며, 목표 상태와 다르면 현재 스위치와 인접한 스위치를 모두 뒤집는다.
   • 첫 번째 경우에서는 첫 번째 스위치를 누른 상태로 초기화한다.
   • 두 번째 경우에서는 첫 번째 스위치를 누르지 않은 상태로 초기화한다.
   • 각 경우에 대해 현재 스위치와 목표 상태를 비교하고, 다르면 스위치를 뒤집는다.
   • 모든 스위치를 검사한 후 마지막 스위치의 상태가 목표 상태와 일치하는지 확인한다.
   • 두 경우 중 유효한 경우의 최소 누름 횟수를 출력다.
4. 최종적으로 두 경우에서의 스위치 누름 횟수를 비교하여 최소 값을 구한다.

O(n)  시간복잡도

 

입력된 전구의 개수 n에 대해 두 번의 반복이 발생하므로 선형 시간복잡도가 소요된다.

전체코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 스위치의 개수
        int n = Integer.parseInt(br.readLine());

        int ans1 = 1, ans2 = 0, INF = 987654321;

        // 현재 상태와 예상 상태를 읽음
        String now = br.readLine();
        String expect = br.readLine();

        // 두 가지 경우의 현재 상태를 저장할 배열과 예상 상태를 저장할 배열
        int[] now_arr_1 = new int[n];
        int[] now_arr_2 = new int[n];
        int[] expect_arr = new int[n];

        // 입력 문자열을 기반으로 현재 상태와 예상 상태 배열을 초기화
        for (int i = 0; i < n; i++) {
            now_arr_1[i] = now.charAt(i) - '0'; // 첫 번째 경우의 현재 상태
            now_arr_2[i] = now.charAt(i) - '0'; // 두 번째 경우의 현재 상태
            expect_arr[i] = expect.charAt(i) - '0'; // 예상 상태
        }

        // 첫 번째 경우의 첫 번째와 두 번째 스위치를 뒤집음
        now_arr_1[0] = 1 - now_arr_1[0];
        now_arr_1[1] = 1 - now_arr_1[1];

        // 스위치를 순회하며 상태를 확인
        for (int i = 1; i < n; i++) {
            // 첫 번째 경우에서 현재 스위치가 예상 상태와 다르면
            if (now_arr_1[i - 1] != expect_arr[i - 1]) {
                // 현재와 다음 스위치를 뒤집음
                now_arr_1[i - 1] = 1 - now_arr_1[i - 1];
                now_arr_1[i] = 1 - now_arr_1[i];
                ans1++; // 뒤집은 스위치 수 증가
                if (i != n - 1) {
                    now_arr_1[i + 1] = 1 - now_arr_1[i + 1]; // 마지막 스위치가 아니면 다음 스위치도 뒤집음
                }
            }

            // 두 번째 경우에서 현재 스위치가 예상 상태와 다르면
            if (now_arr_2[i - 1] != expect_arr[i - 1]) {
                // 현재와 다음 스위치를 뒤집음
                now_arr_2[i - 1] = 1 - now_arr_2[i - 1];
                now_arr_2[i] = 1 - now_arr_2[i];
                ans2++; // 뒤집은 스위치 수 증가
                if (i != n - 1) {
                    now_arr_2[i + 1] = 1 - now_arr_2[i + 1]; // 마지막 스위치가 아니면 다음 스위치도 뒤집음
                }
            }
        }

        // 마지막 스위치의 상태가 예상 상태와 다른지 확인
        if (now_arr_1[n - 1] != expect_arr[n - 1]) ans1 = INF; // 첫 번째 경우 실패
        if (now_arr_2[n - 1] != expect_arr[n - 1]) ans2 = INF; // 두 번째 경우 실패

        // 최소한의 스위치 뒤집기 횟수를 출력하거나, 두 경우 모두 불가능할 때 -1을 출력
        if (ans1 == INF && ans2 == INF)
            System.out.println(-1);
        else
            System.out.println(Math.min(ans1, ans2));
    }
}