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

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

문제

전구와 스위치 문제 링크

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은 꺼져 있는 상태를 의미한다.

3
000
010

출력

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

3

접근 방식

같은 스위치를 두 번 이상 누르는 경우는 없다

1. 가장 왼쪽의 스위치를 킨 것과 키지 않은 두 가지 경우로 나눈다
2. 각 경우에 대해 2번째 스위치부터 시작해서 해당 스위치의 왼쪽과 목표 전구 상태를 비교하며 스위치를 켤지 켜지 않을지 정한다
3. 모두 탐색 후에 두 경우 다 목표 전구 상태와 일치할 경우 둘 중 스위치를 적게 누른 값을 출력하고 둘 중 하나만 일치하면 해당 누른 값을 출력, 둘 다 목표 전구 상태와 일치하지 않을 경우 -1을 출력한다

코드

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

public class Main_2138_정현명 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		String nowBulbStr = br.readLine();
		boolean[] nowBulb_firstO = new boolean[N];
		boolean[] nowBulb_firstX = new boolean[N];
		for(int i=0;i<N;i++) {
			if(nowBulbStr.charAt(i)=='0') {
				nowBulb_firstO[i] = true;
				nowBulb_firstX[i] = true;
			}
		}
		
		String targetBulbStr = br.readLine();
		boolean[] targetBulb = new boolean[N];
		
		for(int i=0;i<N;i++) {
			if(targetBulbStr.charAt(i) == '0')targetBulb[i] = true;
		}
		
		
		int cnt_firstO = 1;
		int cnt_firstX = 0;
		
		nowBulb_firstO[0] = !nowBulb_firstO[0];
		nowBulb_firstO[1] = !nowBulb_firstO[1];
		
		for(int i=1;i<N;i++) {
			if(nowBulb_firstO[i-1] != targetBulb[i-1]) {
				nowBulb_firstO[i-1] =!nowBulb_firstO[i-1];
				nowBulb_firstO[i] = !nowBulb_firstO[i];
				if(i != N-1) {
					nowBulb_firstO[i+1] = !nowBulb_firstO[i+1];
				}
				cnt_firstO++;
			}
			if(nowBulb_firstX[i-1] != targetBulb[i-1]) {
				nowBulb_firstX[i-1] =!nowBulb_firstX[i-1];
				nowBulb_firstX[i] = !nowBulb_firstX[i];
				if(i != N-1) {
					nowBulb_firstX[i+1] = !nowBulb_firstX[i+1];
				}
				cnt_firstX++;
			}
		}
		if(Arrays.equals(nowBulb_firstO,targetBulb) && Arrays.equals(nowBulb_firstX,targetBulb)) System.out.println(Math.min(cnt_firstO, cnt_firstX));
		else if(Arrays.equals(nowBulb_firstO,targetBulb)) System.out.println(cnt_firstO);
		else if(Arrays.equals(nowBulb_firstX,targetBulb)) System.out.println(cnt_firstX);
		else System.out.println(-1);
		
		
		
	}

}