99클럽 코테 스터디 28일차 TIL, 그리디(Iterator for Combination)

1. 문제 정의

2. 문제 접근

할 수 있는 만큼 flip을 시켜주면 되므로 greedy를 이용한다.

3. 문제 풀이

1. 처음 '0'부터 비교 문자를 시작한다.
2. 인덱스가 0부터 이전 문자와 비교하여 다르면 count를 1 증가시킨다.
3. count를 리턴한다.

4. 코드

class Solution {
    public int minFlips(String target) {
        char[] array = target.toCharArray();
        
        int count = 0;
        char prev = '0';

        for(int i = 0; i < array.length; ++i) {
            if(prev != array[i])
                count++;

            prev = array[i];
        }

        return count;
    }
}

 

5. 회고

만약 10101 이 우리가 원하는 문자열이라고 생각해보자. 우리는 00000 부터 시작하므로

00000

111111

10000

10111

10100

10101

이렇게 변하게 된다.

잘 살펴보면 결국 이전 문자랑 다를 경우 count를 올려서 flip을 하는걸 알 수 있다.

문제 풀이는 간단하지만 이런 규칙을 찾는게 생각보다 어려운 것 같다...