[LeetCode] 926번 Flip String to Monotone Increasing 문제를 풀어보았다. (ft. java)

2023년 01월 17일 화요일 - 아니 개 추워!!!!!

오늘 올려볼 문제는 926번 Flip String to Monotone Increasing 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

간단해보였지만 생각보다는 오래걸렸다..

입력

사진에서도 볼 수 있듯이 String 1개가 입력으로 들어온다.

---

풀이 및 코드

Monotone Increasing한 String으로 만들기 위해서 각 원소를 뒤집으라는 문제다.

Monotone Increasing을 찾아봐도 잘 모르겠지만 대충 지수적으로 늘어나는 느낌인 것 같다.

여기서는 "0000", "0001", "0011", "0111", "1111" 처럼 아예 0이나 1로 이루어져 있거나 뒤에가 1로 채워져 있는 상태를 말한다.

오늘은 처음부터 정답을 생각해냈다.

일단 0개수 1개수를 세고 String을 순회한다.

0이 나오면 지나가고 1이 나오면 앞으로 남은 것들 중에 어떤 숫자를 뒤집어야지 작은게 나오는지 계산한다.

이렇게 최소값을 찾아나가는 방향으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        var oneZero = new int[2];
        
        for(int i = 0; i < n; i++) oneZero[s.charAt(i) == '1' ? 1 : 0]++;

        int result = Math.min(oneZero[0], oneZero[1]), flipedOnes = 0;
        
        for(int i = 0; i < n; i++) {
            oneZero[s.charAt(i) == '1' ? 1 : 0]--;
            
            if(s.charAt(i) == '0') continue;
            
            result = Math.min(result, flipedOnes++ + Math.min(oneZero[0], oneZero[1] + 1));
        }
        
        return result;
    }
}

---

제출 화면

저기서 0개수 1개수를 세지않고 그냥 순회 한 번 더 하려고 했었다가 TLE 떠서 개수 기억하게끔 후다닥 바꿨다.

간단해보이지만 생각보다 어려운 것 같다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.