백준 13413 - 오셀로 재배치 (자바 - 그리디)

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

13413번: 오셀로 재배치

 

* 문제 요약

로봇 동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다.

이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다.

목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다.

아래의 예시를 참고하자.

- 초기 상태 : WBBWW

- 목표 상태 : WBWBW

 

로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다.

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.

2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

위의 예시에서 3번째와 4번째 말을 2번 작업을 통해 각각 뒤집으면 2번의 작업으로 목표 상태를 만들 수 있다.

하지만 1번 작업을 통해 3번째와 4번째 말을 골라 서로의 위치를 바꾸어주면 1번만에 목표 상태에 도달할 수 있다.

초기 상태의 말과 목표 상태의 말이 주어질 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 프로그램을 작성하시오.

 

* 입력

입력은 T 개의 테스트 데이터로 구성된다.

각 입력의 첫번째 줄에는 오셀로 말의 갯수 N (1 <= N <= 100,000) 이 주어진다.

각 입력의 두번째 줄과 세번째 줄에는 각각 오셀로 말의 초기 상태와 목표 상태가 주어진다.

초기 상태와 목표 상태의 말의 갯수는 항상 N 과 일치한다.

흰색 면이 보이는 경우에는 W, 검은색 면이 보이는 경우에는 B 로 주어진다.

 

* 출력

입력받은 데이터에 대해, 한 줄에 1개씩 초기 상태에서 목표 상태를 만들기 위한 작업의 최소 횟수를 구한다.

 

* 예시

 

* 해결 과정

이 문제를 처음 풀었을 땐 임의의 2개의 말의 위치를 바꿀 수 있다는 조건 때문에 서로 바꿨을 때 둘 다 목표 상태의 말의 색깔과 일치하게 되는 말을 찾아주기 위해 이중 반복문을 활용했었다.

그러다 보니 통과 판정은 받았으나 2300ms 가 넘는 꽤 긴 처리 시간이 걸려버렸다.

처리 시간이 기하급수적으로 길어진 핵심 원인은 아마 이중 반복문으로 로직을 처리해버렸기 때문일 것이다.

 

* 처리 시간이 2300ms 가 넘어가버린 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tcCount = Integer.parseInt(br.readLine());
        for (int i = 0; i < tcCount; i++) {
            int arrayLength = Integer.parseInt(br.readLine());
            int result = 0;

            StringBuilder before = new StringBuilder(br.readLine());
            StringBuilder after = new StringBuilder(br.readLine());

            for (int j = 0; j < arrayLength; j++) {
                if (before.charAt(j) != after.charAt(j)) {
                    // 문자열내의 임의의 문자와 바꿨을 때 완성된 문자열의 인덱스와 같아질 수 있는지 확인한다.
                    // 단, 여기서 확인 대상은 현재 인덱스와 마찬가지로 완성된 문자열의 인덱스와 서로 다른 경우에 해당한다.
                    boolean check = false;
                    for (int x = j + 1; x < arrayLength; x++) {
                        if (before.charAt(j) != before.charAt(x)) {
                            if (before.charAt(x) != after.charAt(x)) {
                                char temp = before.charAt(j);
                                before.setCharAt(j, before.charAt(x));
                                before.setCharAt(x, temp);
                                check = true;
                                break;
                            }
                        }
                    }

                    // 임의의 인덱스와 위치를 변경하지 못했을 경우 현재 인덱스 값을 뒤집어주기만 하고 끝낸다.
                    if (!check) {
                        before.setCharAt(j, after.charAt(j));
                    }

                    result++;
                }
            }
            bw.write(result + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

이를 해결하기 위해 나 보다 더 빠른 시간내에 문제를 해결한 사람은 로직을 어떻게 작성했는지 살펴보았는데 아래와 같은 해법을 발견할 수 있었다.

- 반복문으로 각 인덱스 별로 탐색을 수행하면서 현재 상태와 목표 상태가 서로 다른 경우를 찾으면 아래와 같은 조건문을 수행한다.

  - 현재 탐색중인 인덱스의 값이 W 이면 W 의 숫자를 세는 변수의 값을 1 증가시킨다.

  - 현재 탐색중인 인덱스의 값이 B 이면 B 의 숫자를 세는 변수의 값을 1 증가시킨다.

- 문자열의 끝까지 탐색을 진행한 후 W 의 숫자를 세는 변수, B 의 숫자를 세는 변수 중 더 큰 값을 정답으로 출력한다.

 

둘 중 더 큰값이 정답이 될 수 있는 이유는 기본적으로 지금 탐색중인 인덱스를 기준으로 현재 상태와 목표 상태가 서로 다른 경우 W 일 때 서로 다른 경우가 더 많은지, 아니면 B 일 때 서로 다른 경우가 더 많은지를 보면 W 와 B 중 목표 상태와 다른 경우가 더 많은 글자가 무엇인지, 그리고 그 갯수가 몇 개인지 알 수 있는데,

다른 경우가 더 많은 글자를 기준으로 잡아야 첫번째 조건인 임의의 2개의 문자의 위치를 바꾸는 행동을 통해 다른 경우가 더 적은 글자와 위치를 모두 바꿔줄 수 있고, 그렇게 한 뒤 남은 글자들은 두번째 조건을 통해 그저 뒤집어 주기만 하면 되기 때문이다.

 

위의 로직이 적용된 코드는 아래와 같다.

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

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tcCount = Integer.parseInt(br.readLine());
        for (int i = 0; i < tcCount; i++) {
            int stringLength = Integer.parseInt(br.readLine());
            int result = 0;

            String before = br.readLine();
            String after = br.readLine();

            int wCount = 0;
            int bCount = 0;

            for (int j = 0; j < stringLength; j++) {
                if (before.charAt(j) != after.charAt(j)) {
                    if (before.charAt(j) == 'W')
                        wCount++;
                    else if (before.charAt(j) == 'B')
                        bCount++;
                }
            }

            result = Math.max(wCount, bCount);
            bw.write(result + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

매 반복단계마다 조건에 맞는 W, 또는 B 의 갯수를 카운팅 한 다음, 최종적으로 현재 상태에서 목표 상태로 변환할 수 있는 선택지를 고르는 식으로 문제를 풀었다.

각 단계마다 글자 갯수를 증가시키는 방식으로 최적의 답을 선택했고, 그 과정의 결과로 본래의 문제가 해결되는 방식으로 문제가 해결되었으므로 그리디 알고리즘 문제에 해당된다.