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

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

난이도

골드4

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

내 코드

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

class Main {
    
    static int N;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String str1 = br.readLine();
        String str2 = br.readLine();

        char[] ver1 = new char[N]; // 첫번째 스위치 안 누름
        char[] ver2 = new char[N]; // 첫번째 스위치 누름

        int cnt1 = 0;
        int cnt2 = 1;

        for(int i = 0; i < N; i++){
            ver1[i] = str1.charAt(i);
            ver2[i] = str1.charAt(i);
        }

        change(ver2, 0);

        for(int i = 1; i < N; i++){
            if(ver1[i-1] != str2.charAt(i-1)){
                change(ver1, i);
                cnt1++;
            }if(ver2[i-1] != str2.charAt(i-1)){
                change(ver2, i);
                cnt2++;
            }
        }

        boolean f1 = isSame(ver1, str2);
        boolean f2 = isSame(ver2, str2);

        if (f1 && f2) {
            System.out.println(Math.min(cnt1, cnt2));
        } else if (f1) {
            System.out.println(cnt1);
        } else if (f2) {
            System.out.println(cnt2);
        } else {
            System.out.println(-1);
        }
    }

    public static void change(char[] arr, int idx){
        for(int i = -1; i < 2; i++){
            if(idx + i >= 0 && idx + i < N){
                arr[idx + i] = arr[idx + i] == '1'? '0' : '1';
            }
        }
    }
    
    public static boolean isSame(char[] arr, String target) {
        for (int i = 0; i < N; i++) {
            if (arr[i] != target.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

그리디는 한번에 생각나지 않으면 뭔가 딱 떠오르지가 않아서 어렵다..

제일 처음을 누르냐 안 누르냐에 따라 원하는 상태를 만드는데 영향을 많이 받기 때문에, 첫번째를 누른 경우와 누르지 않은 경우로 나눠서 카운트를 진행했다.

그리고 앞에서부터 현재 전구가 목표 전구와 일치하지 않다면 바꿔주어야 원하는 목표에 맞춰갈 수 있기 때문에 다르다면 눌러서 전환을 해줘야 한다.

내가 혼란이 왔던 부분은 0번째 일 때를 하나는 누른 상태, 하나는 누르지 않은 상태로 시작을 했는데, for문 에서 1번째에 i-1 인덱스부터 확인을 한다면 다시 0번을 누른 것과 동일하니 결국 ver1과 ver2가 같은 상태를 저장하지 않나? 였다.

하지만 0번을 누르면 0, 1번을 토글하고, 반복문 안에서 i-1번을 확인하고 1번을 토글하는건 토글되는 범위가 달랐던 걸 이해하는데 오래 걸렸던 것 같다.

1번을 change 호출하면 0, 1, 2번이 토글되기 때문에ver1과 ver2이 다를 수 밖에 없다.

처음을 나눠서 시작한다는걸 생각해내는 것도 어려웠는데 구현 부분에서도 헷갈렸던 문제였다.