1529. Minimum Suffix Flips

문제

이번 문제는 문자열과 탐욕 알고리즘을 이해해야 풀 수 있는 문제다.

다음 그림과 같이 눈 앞에 좋은 값만 추출하는 것을 탐욕 알고리즘이라 할 수 있겠다. 우선 어떤 문제인지 살펴보면,

'001011101' 을 입력받았을 때, 입력 받은 자릿 수 길이만큼 '000000000' 을 만들어 주고 '1'과 '0' 만 반전시켜 최대한 적은 횟수로 입력받은 값과 똑같은 값을 만들어줘야 하는 문제다. 그렇다면, 이 문제에 어떻게 해결해야 할까

코드

private static int solution(String target) {
        int answer = 0;
        char check = '0';
        for (int i = 0; i < target.length(); i++) {
            if (target.charAt(i) != check) {
                answer ++;
                check = target.charAt(i);
            }
        }
        return answer;
    }

솔루션을 확인하다 보니 답은 굉장히 간단했다. 굳이 다 바꿔서 문자열끼리 비교하면 된다 한들, 런타임 에러가 발생해 좋지 않은 코드를 작성하기 때문에 연속적인 '1' 혹은 '0'을 확인하면 끝나는 문제이다. 한마디로, 처음부터 검사를 시행해 당장 눈 앞에 다른 숫자만 추출해 answer ++ 을 하면 되는 것이었다.

결과