926. Flip String to Monotone Increasing
https://leetcode.com/problems/flip-string-to-monotone-increasing/
문제
풀이(DFS)
s = "010"일 때 나올 수 있는 경우의 수이다.
위에 그래프 로직은 다음과 같다.
재귀 구조를 돌되 parent와 자기 자신과 비교를 해서 자기 자신이 크거나 같을 때만 재귀 구조를 돌게 한다. 예를 들어 "01"일 때 자기자신이 0이 되어버리면 "010"이 되는데 이것은 Monotone Increasing 조건에 맞지 않기 때문에 탐색할 필요가 없다. 즉 Monotone Increasing 되는 조건으로만 탐색하게 한다.
이렇게 탐색했으면 리턴을 시켜주어야 하는데 주어진 문자열 s와 자기자신을 비교한다. 그래프에서 보면 s = "010"이고 탐색해서 나온 결과 중 "001"이 있는데 s[2] == 1이 아니므로 1을 리턴한다. 백트래킹하여 s[1] == 0을 비교하는데 아니므로 1을 더한 값 2를 리턴한다. 이런식으로 하여 뒤집어진 문자열 개수를 리턴하고 여기서 최소값을 구하면 된다.
결과(DFS)
속도도 많이 느리고 특히 재귀구조를 사용하였기 때문에 메모리부분에서 성능이 많이 떨어진다.
풀이(DP)
포인터를 기준으로 왼쪽은 0 오른쪽은 1이 되도록 하면 된다.
예를 들어 s="00110"일 때 생각해보자
i = 0일 때 left = "", right = "11111"
i = 1일 때 left = "0", right = "1111"
i = 2일 때 left = "00", right = "111"
i = 3일 때 left = "000", right = "11"
i = 4일 때 left = "0000", right = "1"
i = 5일 때 left = "00000", right = ""가 될 것이다.
그래서 dp에는 i(인덱스)마다 0,1의 총 합을 저장해 두고 활용하는 방식으로 구현하였다.
dp에는 다음과 같이 저장될 것인데 i = 2일 때를 생각해보자
left = "00", right = "111"이 되어야 하므로 dp에서 비교를 해야한다.
left일 때에는 i = 1일 때를 봐야 하는데 1이 총 0개 있으므로 바꿀 필요가 없다. 따라서 left = 0이 될 것이고
right일 때에는 마지막 인덱스인 i = 4일 때에서 현재 인덱스인 i=2일 때를 빼주면 된다. right는 1이 될 것이다. 이런식으로 해서 최소값을 구하는 로직이다.
첫 번째 for문에서 dp에 인덱스마다 0,1에 따른 총합을 저장해 두고 left, right를 나누어서 바뀐 개수를 찾고 최소값을 반환하는 로직이다. 아무래도 재귀구조보다 메모리도 적게 쓰고 시간복잡도 측면에서도 n에 가깝다.결과(DP)
풀이(DP_2번째)
결과(DP)
