[BOJ - Silver IV] 오셀로 재배치 / ⭕

 

오셀로 재배치

1. 제출 코드 (12분 32초 / 그리디)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            int w = 0;
            int b = 0;
            String curr = br.readLine();
            String ans = br.readLine();
            for(int j = 0; j < N; j++) {
                if(curr.charAt(j) != ans.charAt(j)) {
                    if(curr.charAt(j) == 'W') {
                        w++;
                    } else {
                        b++;
                    }
                }
            }
            System.out.println(w > b ? w : b);
        }
    }
}

 

2. 구현 로직

1. 오셀로 말의 초기 상태와 목표 상태의 각 원소마다 비교를 진행
2. 만약, 같은 상태가 아닐 떄, 초기 상태의 말이 white이면 w + 1, black이면 b + 1
3. w와 b의 개수가 같으면 서로 교차하는 것이 가장 이상적인 답이며 한쪽의 값이 클 경우에는 추가로 해당 원소만 뒤집으면 된다.

 

3. 유의할 점

• 최소 횟수를 어떻게 구해야할지를 고민해보면 정답을 쉽게 구할 수 있을 거 같다.