백준 2138 | 그리디 알고리즘, 전구와 스위치

이해하지 못하는 내가 너무 답답하다!

SSAFY 준비를 위해 CT(Computer Thinking) 문제를 연습하던 중 카드 뒤집기 문제를 만났다.

카드 뒤집기
N개의 카드가 앞면은 1 뒷면은 0 으로 주어진다.
1번의 '찬스' 를 사용하여 i번째, i-1번째, i+1번째 카드를 동시에 뒤집는다.(1번의 찬스로 인접한 카드까지 뒤집는다.)
카드의 앞,뒷 면 정보가 0과 1 로 주어질 때 모두 뒷면으로 만드는 최소 찬스 개수를 구하여라.

예시)
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
예시답) 3 회
예시풀이)
1회>
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
2회>
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
3회>
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

문제
1번) 0 1 1 1 1 0
2번) 0 0 0 0 1 1 1 1 0
3번) 0 0 1 1 0 1 1 0 1 1 1 0 1
4번) 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0
5번) 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 0

위의 문제인데, 손으로 노가다를 하면 풀 수 있다. 하지만 엄연히 CT 문제인데, 막무가내로 풀면 실전에서 불리할 수 있다는 생각에 어떤 분이 댓글로 설명한 내용을 차근히 읽어보고, 써보고, 그려도 봤다.

 

그런데 도무지 이해가 되지 않았다.
이 문제는 경우의 수를 이용해서 푼다고 하며, 첫 번째 숫자를 뒤집는 경우와 뒤집지 않는 경우를 가지고 최종적인 경우의 수를 파악해서 정답을 맞출 수 있다고 한다.(이 말 조차 이해할 수 없다.)

 

나는 아무리 읽어 봐도 풀이를 이해할 수 없었기 때문에 더 기초 문제를 풀어 보는 것이 좋을 것 같아 BOJ의 2138번 문제를 풀어 보기로 했다.(지옥 시작)

지옥의 시작 : 2138 전구와 스위치

2138번: 전구와 스위치

정말 감사한 블로그

2138번 : 전구와 스위치

이 문제는 위의 CT 문제와 비슷하지만 조금은 다르다.
먼저, 입력한 두 개의 배열(전구의 배열) 중 첫 번째 배열이 두 번째 배열과 같아지기 위해서는 몇 번의 전구 스위치를 눌러야 하는지를 구하는 문제이다.
먼저 확인해야 할 점은 최솟값을 구해야 한다는 것. 즉, 주어진 배열을 처음부터 끝까지 딱 한번만 탐색하여 스위치를 누를 수 있다. 그러니까 같은 인덱스를 두 번 이상 탐색하여 스위치를 누른다는 것은 첫 번째 배열을 두 번째 배열로 만들 수 없다는 의미이다.(라고 모든 개발자 블로그에서 말하더라. 아직도 이해할 수 없음.)

 

i 번째 전구의 스위치를 누르면 i-1, i+1 번째 전구를 끄거나 킬 수 있다. 그렇기 때문에 i 번째 스위치를 끄거나 켜기 위해서 i-1, i, i+1 번째 스위치를 이용해야 한다. 하지만 최소한이라는 조건 때문에 i-1 번째 전구의 스위치를 통해 i 번째 전구를 제어하는 경우의 수는 배제하는 것이 좋다.(그렇게 이해했다.)

 

이 문제를 풀면서 0 번째 전구의 스위치를 눌렀는지 누르지 않았는지를 기준으로 삼는 것이 정말 이해가 가지 않는다. 많은 블로그를 읽어 봐도 이해가 가지 않는다.(진짜 바보다.)

 

가장 많이 참고한 블로거의 게시물을 보면 이런 설명이 있다. (1) i-1 번째 전구를 두 번째 배열의 i-1 번째 전구와 비교하면서 스위치를 눌러야 할지 누르지 말아야 할지를 결정해서 최소한의 경우의 수를 구한다.
단, (2) 0 번째의 경우 -1 번째 전구는 없으니 0 번째를 눌렀을 경우와 누르지 않았을 경우를 비교하여 둘 중 하나의 경우에서 두 번째 배열과 똑같을 때 해당 경우에서 변경된 카운트를 출력하면 된다.

 

만약 두 경우 모두 (3) 두 번째 배열과 같지 않다면 해당 배열은 변경할 수 없기 때문에 -1을 출력한다.

 

여기서 첫 번째, 두 번째 배열의 i-1 번째 전구가 같지 않을 경우 i 번째 전구의 스위치를 눌러 첫 번째 i-1 번째 전구를 두 번째 배열의 i-1 번째 전구와 똑같이 맞춰 준다.

(진짜 웃기다. 글을 읽을 때도, 코드로 작성할 때도(오마주라고 할 수 있다.) 전혀 이해가 되지 않았는데, 내가 직접 글로 쓰니까 하나씩 이해가 되고 있다.)

 

이 설명의 블로거 분께서 작성하신 코드를 보면 0 번째를 눌렀는지 누르지 않았는지를 비교하기 위해 첫 번째 배열을 2차원 배열에 두 번 저장한다.
위의 설명은 카카오톡 스크린샷의 설명과도 동일하다.

이제 코드를 살펴보자.(참고 블로그의 코드와 동일하다.)

package 심성헌.알고리즘_5주차;

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

public class 전구와스위치_2138 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, count, answer;
    static int[][] arr;
    static int[] check;

    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(br.readLine());
        arr = new int[2][n];
        check = new int[n];
        answer = Integer.MAX_VALUE;

        String input = br.readLine();
        String input2 = br.readLine();
        for (int i = 0; i < input.length(); i++) {
            arr[0][i] = input.charAt(i) - '0';
            arr[1][i] = input.charAt(i) - '0';
            check[i] = input2.charAt(i) - '0';
        }
        // arr[0] : 0 번째 전구를 켜지 않는 경우
        play(1, 0, 0);
        // arr[1] : 0 번째 전구를 킨다.
            // arr[1][0], arr[1][1] 전구가 켜진다.
        onoff(0, 1);
        // arr[1] : 0 번째 전구를 킨 상태에서 탐색한다.
        play(1, 1, 1);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[1][i]);
        }
        System.out.println("\n");
        // arr[0] 와 arr[1] 중 최소한의 count를 출력한다.
            // 만약 주어진 조건으로 전구를 바꾸지 못할 경우 -1을 출력한다.
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    // 전구의 전원을 스위치하는 기능
    public static void onoff(int idx, int type) {
        for (int i = idx - 1; i <= idx + 1; i++) {
            if (i >= 0 && i < n)
                arr[type][i] = arr[type][i] == 1 ? 0 : 1;
        }
    }

    // 주어진 전구를 탐색한다.
    // 현재 인덱스의 -1에 해당하는 인덱스가 check와 다른 경우
        // 스위치를 킨다.
        // 다음 play 기능으로 돌아간다.
    // 현재 인덱스의 -1에 해당하는 인덱스가 check와 같은 경우
        // 스위치를 켤 필요가 없으니
        // 스위치를 켜지 않는다.
        // count를 세지 않는다.
    // 현재 인덱스가 n과 같은 경우 인덱스 범위를 넘었기 때문에 리턴
        // 만약 n-1의 arr와 check의 인덱스 값이 같은 경우
            // answer는 count보다 작을 경우 count 값이 되고,
            // 아닐 경우에는 answer 값그대로.
    public static void play(int idx, int type, int count) {
        if (idx == n) {
            if (arr[type][idx - 1] == check[idx - 1])
                answer = answer > count ? count : answer;
            return;
        }
        for (int i = 0; i < n; i++) {
            System.out.print(arr[type][i]);
        }
        System.out.println();
        System.out.println("---------------");
        if (arr[type][idx - 1] != check[idx - 1]) {
            onoff(idx, type);
            play(idx + 1, type, count + 1);
        } else
            play(idx + 1, type, count);
    }
}

코드를 쓰면서도 이해가 가지 않아서 주석을 많이 작성했다.
원래 코드는 입력값을 char 자료형으로 받았으며, String 자료형에서 charOfArray()라는 메소드를 통해 문자열 자체를 배열로 만들었는데 이번에 알게 되어서 정말 새로웠다.

 

다른 블로그에서는 완전 탐색을 할 수 없으니 재귀 함수를 사용했을 때 시간 복잡도에 의해 시간 초과 결과를 출력한다고 하는데, 이 분은 그 한계를 뛰어 넘으셨다. 정말 대단하다고 생각한다.

 

이번 문제를 풀면서(내가 풀진 않고 이해하면서) 시간 복잡도를 먼저 이해하고 문제를 접근하는 것이 중요하다고 생각됐다. 왜냐하면 저번 주차 문제 중 정렬 문제를 풀 때도 시간 복잡도 때문에 문제를 맞추지 못했다.(접근법이 잘못됐다.)

 

항상 느끼지만 언제쯤 문제를 온전히 이해해서 내가 직접 코드를 구현할 수 있을까? 사실 문제를 처음 보면 머릿속으로 그려지기는 하지만 이걸 코드로 구현할 수 없는데, 그럴 때 너무 화가 난다.(love myself..❤️)

그러니까 나한테 화 내지 않으려면 더 열심히 공부하는 수 밖에 없다.
아자 아자 화이팅..!😇