99클럽 코테 스터디 30일차 TIL Minimum Suffix Flips
https://leetcode.com/problems/minimum-suffix-flips/description/
깊은 복사
그리디 알고리즘
1. 문제 및 접근
1과 0으로 구성된 타겟 스트링이 들어오면 같은 길이의 0으로 이루어진 s를 타겟이랑 같이 만들고 싶다
/한번 연산 0부터 시작하는 i~n-1까지의 인덱스를 한번에 바꿀 수 있다 (시작부터 끝까지 다 바꿈)
0 -> 1, 1-> 0
s를 target과 동일하게 만들기 위한 최소 연산
순서는 어떤 걸 먼저 하냐보다 012 201 120 이 흐름에만 맞으면 됨x
탐색을 어디서 하든 상관 x일 거 같다 그러면 0으로 시작한다면 다음 수가 뭔지를 찾아야함
근데 000 -> 001로 바꾸는 경우에는 3부터 무조건 시작해야 하잖아
그러면 최초의 1부터 바꿔나가자 그냥 한번씩 brute force를 쓰지 않고 바꾸려면 ?
ex)
000 -> 101
000 -> 111 1번부터, -> 001 3번부터 , -> 001 3번부터 , -> 011 2번부터 -> 011 2번부터
111 -> 100 2번부터, -> 010 2번부터 , -> 110 1번부터 , -> 100 1번부터 -> 010 3번부터
100 -> 101 3번부터 , -> 101 1번부터, -> 1 01 2번부터 , -> 101 3번부터 -> 101 1번부터
00000 -> 10111
00000 -> 00111, i=2부터 n-1까지 바꾸고, 1
00111 -> 11000, i=0부터 n-1 2 11111 -> 10000 -> 10111
11000 -> 10111, i=1부터 n-1 3 01111 -> 01000 -> 10111
현재 수가 더 앞의 index의 영향을 받게 된다.
Constraints:
- n == target.length
- 1 <= n <= 10^5
- target[i] is either '0' or '1'
2. 풀이
먼저 현재 수와 다르다면 전체를 다 뒤집는 방법을 생각했는데
이렇게 한다면 O(N^2)인데, 최대 100억.. 안된다..
다른 방법이 안 떠올라서 일단 O(N^2)로 먼저 구현해봤다..
이 풀이로 풀면 다른 방법이 볼까 싶어서..
2. O(N^2) 풀이 *틀림"
targer = "10111" 을 예시로 보자면
먼저
sArr {0,0,0,0,0} (깊은 복사)
targer {1,0,1,1,1}로 초기화
String 값보다 배열로 접근이 더 편하고 좋아보였다.
(boolean이 더 좋을 것 같지만, 사실 char도 숫자라 상관없긴 하지만 더 편해)
현재 수가 바꿀 s의 [i]와 다르다면, answer을 하나 올려주고,
s의 전부를 바꾸는 for문을 반복한다.
역시나,
3. N(O) 풀이
import java.util.Arrays;
public class minimumSuffixFlips {
//1과 0으로 구성된 타겟 스트링이 들어오면 같은 길이의 0으로 이루어진 s를 타겟이랑 같이 만들고 싶다
//한번 연산 0부터 시작하는 i~n-1까지의 인덱스를 한번에 바꿀 수 있다 (시작부터 끝까지 다 바꿈)
// 0 -> 1 1-> 0
//s를 target과 동일하게 만들기 위한 최소 연산
// 00000 -> 10111
// 00000 -> 00111, i=2부터 n-1까지 바꾸고, 1
// 00111 -> 11000, i=0부터 n-1 2 11111 -> 10000 -> 10111
// 11000 -> 10111, i=1부터 n-1 3 01111 -> 01000 -> 10111
//순서는 어떤 걸 먼저 하냐보다 012 201 120 이 흐름에만 맞으면 됨x
//탐색을 어디서 하든 상관 x일 거 같다 그러면 0으로 시작한다면 다음 수가 먼지를 찾아야함
// 근데 000 -> 001로 바꾸는 경우에는 3부터 무조건 시작해야 하잖아
// 그러면 최초의 1부터 바꿔나가자 그냥 한번씩 brute force를 쓰지 않고 바꾸려면 ?
// 000 -> 101
// 000 -> 111 1 001 3 001 3 011 2 011 2
// 111 -> 100 2 010 2 110 1 100 1 010 3
// 100 -> 101 3 101 1 101 2 101 3 101 1
// 현재 수가 더 앞의 index의 영향을 받게 된다.
public static void main(String[] args) {
String target = "10111";
minimumSuffixFlips main = new minimumSuffixFlips();
System.out.println(main.minFlips(target));
}
public int minFlips(String target) {
int length = target.length();
int arr[] = new int[length];
// int sArr[] = Arrays.copyOf(arr, length);
for (int i = 0; i < length; i++) {
arr[i] = target.charAt(i) - 48; // 48보다 더 쌈뽕한 것 ?
}
int answer = 0;
int now = 0;
// for (int i = 0; i < length; i++) {
//
// if (arr[i] != sArr[i]) {
//
// answer++;
// sArr[i] = arr[i];
//
// for (int j = i; j < length; j++) {
//
// if (sArr[j] == 1) {
// sArr[j] = 0;
//
// } else
// sArr[j] = 1;
// }
// }
// }
for (int i = 0; i < length; i++) {
if (arr[i] != now) {
answer++;
now = arr[i];
}
}
return answer;
}
}
접근은 전체를 바꿀 필요가 없다..
현재 수만 고려하는 그리디 알고리즘으로 접근하면 되는데,
3-1. 배열 복사
arr[] = {1,0,1,1,1}
target = "10111" 을 int 타입의 수로 넣어주기 (-48)
정답을 셀 answer과
현재 i번째 수가 0 or 1 판별할 now
3-2. 0과 1 뒤집기
들어온 String의 숫자만큼 돌면서,
현재 arr[1,0,1,1,1]에서 i번 째가 now 같지 않다면 ?
count++
now를 현재 수로 저장 0 or 1의 값
3-3. 2번 풀이처럼 전체를 뒤집지 않고 어떻게 가능하냐 ?
실제로 문자열 전체를 뒤집지 않아도 현재 상태에서 출발해 추적해서 불필요한 연산을 줄일 수 있다.
연속된 0 or 1가 동일할 경우에는 중간에서 바꿔도 결과는 동일하기 때문
즉 현재 담은 직전의 수(now)와 다음 배열의 i가 다르기만 하다면 바꿔 주는 것
전체를 바꿀 필요가 x
예를 들어
[1, 0, 1, 1, 1]의 값을 가진 목표 배열 : target = {1, 0, 1, 1, 1}
현재 값만 담을 : now = 0,
직관적으로 보기 위한 now를 전체 다 바꿨을 때의 배열 : now = {0, 0, 0, 0, 0} ,
정답을 count 해줄 count = 0
4개의 경우로 예를 들겠다.
1. target[0]인 1이 now의 0과 다름
- target[1, 0, 1, 1, 1] , now = 0 , now = {0, 0, 0, 0, 0}
- now를 1로 바꿔주고, count = 1
- now = 1, now = {1, 1, 1, 1, 1}
2. target[1]인 0이 now의 1과 다름
- target[1, 0, 1, 1, 1] , now = 1 , now = {1, 1, 1, 1, 1}
- now를 0으로 바꿔주고, count = 2
- now = 0, now = {1, 0, 0, 0, 0}
3. target[2]인 1이 now의 0과 다름
- target[1, 0, 1, 1, 1] , now = 0 , now = {1, 0, 0, 0, 0}
- now를 1으로 바꿔주고, count = 3
- now = 1, now = {1, 0, 1, 1, 1}
3. target[3]인 1이 now의 1과 같음
- target[1, 0, 1, 1, 1] , now = 1 , now = {1, 0, 1, 1, 1}
- 같으니 다음 i로 continue;
3. target[4]인 1이 now의 1과 같음
- target[1, 0, 1, 1, 1] , now = 1 , now = {1, 0, 1, 1, 1}
- 같으니 for문 종료
예시를 보면 0의 값으로 시작해 현재 문자열을 바꾸고 now에 현재 값을 저장한다면,
초기 now 배열이 연속된 배열이고, 차례대로 진행된다면 바꾼 현재 값으로 모든 배열의 플립으로 처리가 되게끔 가능하다.
이걸 직관적으로 생각해내서 시간복잡도를 줄여야 한다니.. 내 탓이오..
4. 마무리
수학적인 사고 방식으로 생각 하는 걸 좋아한다고 생각했고, 모든 상황에 경우의 수를 항상 계산해왔는데
일상생활이 아닌, 수학에서의 경우의 수를 다 따지기엔 너무 방대해서 놓치는 부분이 많은 것 같다..
문제를 풀 때 다른 해답이 떠오르지 않는다면,
시간복잡도에 의해서 걸리더라도 할 수 있는 방법으로 일단 풀어봐야겠다..
그러다 번뜩이고 아이디어가 떠오를 수 있으니까~