[코테연습] 1529. Minimum Suffix Flips

이번 문제는 배열 문제였다.

이 문제를 풀면서 든 생각은 '속았다' 였다.

나 자신을 나 스스로 속인 건지, 아니면 문제의 의도가 그랬던건지는 모르겠지만...

이 문제를 풀기 위해서 처음에 백트래킹으로 접근했다.

0과 1을 계속 flip 을 구현하여 뒤집으면서 target 과 동일한 string 값이 나올때까지 계속 '완전탐색' 하는 것이다.

하지만 문제를 살짝 가볍게 바라보면 이 문제는 '몇 번' 뒤집었는지 파악하는 'greedy' 문제에 가깝다는 것을 알 수 있다.

000000000 비트값이

001011101 이 되기 위해서

'몇 번' 뒤집었는지 '셀 수' 있는 것이다.

0에서 1이 되기 위해서는 한번 뒤집어야한다. 그리고 1에서 0이 되기위해서도 한번 뒤집어야한다.
해당 flip 을 시뮬레이션해보면 다음과 같다.

001111111
001000000
001011111
001011100
001011101

즉, 연속해서 같은 번호는 건너뛰고 그 전 값과 다른 값이면 뒤집는 횟수를 구할 수 있는 것이다.

코드로 구현하면 다음과 같다.

이때, 첫번째 index = 0  이 1이냐 0이냐에 따라서 시행횟수는 달라진다.

 

class Solution {
   
    public int minFlips(String target) {
        
        String[] arr = target.split("");
        int count = arr[0].equals("0") ? 0 : 1;

        for (int i = 1 ; i < arr.length; i++) {
            String prev = arr[i-1];
            String now = arr[i];
            if (!prev.equals(now)) {
                count++;
            }
        }
        return count;
    } 
     

}