[백준 2138번] 전구와 스위치 (Java 자바) 풀이 방법

백준 2138번 <전구와 스위치> 문제 보기

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

2138번: 전구와 스위치

 

 

백준 2138번 <전구와 스위치> 문제 풀이

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

public class Main {
    
    private static int N, check1, check2;
    private static String start, end;
    private static int[] arr1, arr2, result;
    
    public static void main(String args[]) throws IOException {
      
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        start = br.readLine();
        end = br.readLine();
        
        arr1 = new int[N];
        arr2 = new int[N];
        result = new int[N];
        
        check1 = 0;
        check2 = 0;
        
        for(int i=0; i<N; i++){
            arr1[i] = start.charAt(i) - '0';
            arr2[i] = start.charAt(i) - '0';
            result[i] = end.charAt(i) - '0';
        }
        
        swap(arr2, 0);
        check2++;
        
        for(int i=1; i<N; i++){
            if(arr1[i-1] != result[i-1]){
                swap(arr1, i);
                check1++;
            }
            if(arr2[i-1] != result[i-1]){
                swap(arr2, i);
                check2++;
            }
        }
        
        if(check(arr1, result) && check(arr2, result)){
            check1 = (check1 < check2) ? check1 : check2;
            System.out.println(check1);
        } else if(check(arr1, result)){
            System.out.println(check1);
        } else if(check(arr2, result)){
            System.out.println(check2);
        } else{
            System.out.println(-1);
        }
        
        bw.flush();
        bw.close();
        
    }
    
    private static void swap(int[] arr, int i) {
        
        if(i > 0){
            if(arr[i-1] == 1) arr[i-1] = 0;
            else arr[i-1] = 1;
        }
        
        if(arr[i] == 1) arr[i] = 0;
        else arr[i] = 1;
        
        if(i == N-1) return;
        
        if(arr[i+1] == 1) arr[i+1] = 0;
        else arr[i+1] = 1;
        
        return;
    }
    
    private static boolean check(int[] a, int[] b){
        for(int i=0; i<N; i++){
            if(a[i] != b[i]){
                return false;
            }
        }
        return true;
    }
    
}

 

• 접근 방식
  • 처음에는 BFS를 이용하여 queue에 스위치 변경을 통해 나올 수 있는 경우의 수를 for 반복문을 통해 모두 넣고 일치하는 경우가 있을 때까지 while문을 반복하도록 하려고 했다.
  • 이전 위치를 또 바꾸는 일이 없도록 위치를 따로 저장시켜야 한다는 점에서 다른 방법을 고안해보게 되었다.
  • 다른 풀이를 보고 공부를 하면서, 시작 지점을 전구가 켜진 상태와 꺼진 상태, 2가지로 나누고 이를 기준으로 오른쪽으로 스위치를 하나씩 바꿔가며 답안과 맞춰봤을 때 마지막 경우에 일치한다면 스위치를 켰던 횟수를 반환해주면 되는 것을 깨달을 수 있었다.

 

 

✔️ 보라색 부분 : 스위치를 눌러서 바뀌는 전구 3개 위치

✔️ 파란색 점선 : 답안과 일치하게 맞춰놓은 부분

 

 

 

 

• 코드 설명
  • arr1 배열을 통해 0으로 시작하는 전구를 기준으로 탐색
  • arr2 배열을 통해 1로 시작하는 전구를 기준으로 탐색
  • swap 함수를 통해 해당 위치 i에서 i 위치의 전구를 포함하여 i-1 위치와 i+1 위치의 전구도 함께 상태를 바꿔줌
  • check 함수를 통해 두 배열의 각각 원소값이 모두 일치하는지 확인

 

 

• 후기
  • 초등학교 때 사고력 기르는 수학 공부하던 당시 비슷한 문제를 공부했던 기억이 어렴풋이 났다. 이럴 때 기억해야 쓸모있는건데... 아쉬움도 크고 내 자신에 대한 실망감도 좀 있었던 거 같다. 이런 문제를 풀면서 수학적 사고가 중요하단 생각이 문득 드는 거 같다.
  • 최근에 회사 다니면서 알고리즘 공부는 아예 안 했었는데, 이번에 Java로 주 언어를 바꾼 만큼 여름에 더 시간 들여서 공부해야겠다는 생각을 했다.
  • 어려운 문제를 피하지 않고 부딪히는 연습을 더 많이 해야겠다.