코드트리 [자바 java] G & H 반전시키기

https://www.codetree.ai/missions/8/problems/reversing-g-and-h?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 그리디 중 상태반전이 가능한 문제에 해당한다.

 

<구간 단위로 반전시키기>

 

 

위와 같이, 문자열이 주어지고, 구간 단위로 뒤집을 수 있을 때(0은 1로, 1은 0으로) 최소한의 횟수로 뒤집어서 원하는 문자열을 만드는 문제가 있다고 하자. 

 

첫번째 방식과 같이 전체를 뒤집은 후, 특정 구간을 뒤집는 것도 가능하지만, 밑에처럼 원하는 배열과 다른 구간만 뒤집는 경우도 가능하다. 어떤 수를 뒤집고, 또 뒤집으면 원래의 자기 자신으로 돌아오므로, 이와 같은 반복은 최대한 일어나지 않게 하는 것이 좋다. 따라서 일치하지 않는 문자의 구간의 수가 최소한의 횟수와 같다고 볼 수 있다.

 

위와 같은 원리로, 두 문자열에서 같지 않은 값을 가지는 구간의 수를 세는 과정을 거쳤다.

 

String을 char형태로 변환하고, 

앞에서부터 배열을 차례로 탐색했다. arr에다가 두 배열이 같으면 1을, 다르면 0을 넣는다.

현재 탐색하고 있는 index의 두 char값이 같으면 0을 넣고, 다르면 1을 넣은 후 이전의 arr의 값이 1이면 새로운 구간의 시작이므로 답에 1을 더한다.

 

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        String f = br.readLine();
        String s = br.readLine();

        char[] ff = f.toCharArray();
        char[] ss = s.toCharArray();

        int[] arr = new int[ff.length];

        int ans = 0;

        //arr이 0이면 다르다, 1이면 같다

        if(ff[0] != ss[0]){
            arr[0] = 0;
            ans++;
        }
        else{
            arr[0] = 1;
        }

        for(int i = 1;i<ff.length;i++){
            if(ff[i] == ss[i]){
                arr[i] = 1;
            }
            else{
                if(arr[i-1] == 1) ans++;
            }

           // System.out.println(ff.length);

        }

        System.out.println(ans);

    }
}