99클럽 코테 스터디 30일자 TIL + minimum-suffix-flips

문제 출처

https://leetcode.com/problems/minimum-suffix-flips (leetcode)

학습 키워드

배열

시도 방법

문자의 처음부터 시작해서 서로 다르면 flip을 하도록 했다.
단, 처음에는 반복문을 이용하면서 실제로 00000 01111 01000 이런식으로 데이터를 만들어갔는데 시간초과가 발생했다.
굳이 만들 필요없이 충분히 문제를 해결할 수 있다.

내가 작성한 코드

class Solution {
    public int minFlips(String target) {

        char now = '0'; 
        int count = 0 ; 

        for(int i = 0 ; i<target.length(); i++) {
        
            if(now != target.charAt(i)) {
                now = (now == '0') ? '1' : '0' ; 
                count++; 
            }
        }
        return count;           
    }

}

코드설명

가장 처음 상태는 target 길이와 동일한 00000...이다.

그러다가 target과 다른 순간이 오면 그 뒤의 내용을 모두 flip한다.

예를 들어 target이 001000 이라면 001111 형태가 된다.

중요한 건 이걸 굳이 모두 구현하지 않고 상태만 들고 있으면 된다는 것이다.

왜냐면 그 뒤의 내용이 모두 동일하게 값을 가져가기 때문이다(압축개념)

예) target = 00100

현재 상태값 (char) : 0

진행하다가 1을 만나면 사실상 00111 이지만 그냥 상태값만 1로 변경

현재 상태값 (char) : 1

진행하다가 0을 만나면 사실상 00100 이지만 그냥 상태값만 0으로 변경

이렇게 flip을 진행해서 시간 내에 원하는 목표 플립을 구할 수 있다.

출력결과

새롭게 알게된 점

없음

다음에 풀어볼 문제 - top-k-frequent-elements

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL