[백준OJ] 13413번 오셀로 재배치

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

13413번: 오셀로 재배치

---

 

풀이

2가지 작업중 하나를 골라서 최소 횟수로 원하는 목표상태를 만들어야 합니다.

따라서 초기상태와 목표상태를 비교하여 Black -> White 의 개수와 White -> Black의 개수를 카운트 해준 뒤, 짝을 맞춰서 맞는짝은 1번작업을, 나머지는 2번작업을 해줍니다.

 

예를들어 아래와 같은 상황인 경우

WBBWW
WBWBW

Black -> White 의 개수는 1개, White -> Black 의 개수는 1개입니다. 따라서 1번 작업을 통해 서로를 바꿔주면 1번만에 해결됩니다.

 

다음 예시를 보면

BBBBBBB
BWBWBWB

B -> W 는 3개, W -> B는 0개입니다. 아무리 1번작업을 여러번 한다해도 맞출 수 없기때문에 2번작업을 3번 해줘서 목표를 맞추는 방법뿐입니다.

 

마지막 예시를 보면

WWBB
BBWB

B -> W 는 2개, W -> B는 2개입니다. 따라서 짝맞춰서 1번작업을 2번해주면 목표를 만들 수 있습니다.

 

시간복잡도

테스트케이스를 제외하면, 선형시간이 걸리기때문에 O(N)이 됩니다.

 

코드

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.valueOf(br.readLine());
        while (t-- > 0) {
            int n = Integer.valueOf(br.readLine());

            String str1 = br.readLine();
            String str2 = br.readLine();

            int blackToWhite = 0;
            int whiteToBlack = 0;

            for (int i = 0; i < n; i++) {
                if(str1.charAt(i) != str2.charAt(i)){
                    if(str1.charAt(i)=='B'){
                        blackToWhite++;
                    }
                    else{
                        whiteToBlack++;
                    }
                }
            }

            int answer = Math.min(blackToWhite,whiteToBlack) + Math.abs(blackToWhite-whiteToBlack);
            System.out.println(answer);
        }
    }
}