[코딩테스트 일지 - 99클럽] 17일차 - Minimum Suffix Flips
코딩 테스트 준비 일지 17 일차
응시 사이트 : LeetCode
문제 : Minimum Suffix Flips
난이도 : 중하
풀이시간 : 1h 03m
You are given a 0-indexed binary string target of length n. You have another binary string s of length n that is initially set to all zeros. You want to make s equal to target.
In one operation, you can pick an index i where 0 <= i < n and flip all bits in the inclusive range [i, n - 1]. Flip means changing '0' to '1' and '1' to '0'.
Return the minimum number of operations needed to make s equal to target.
Example 1:
Input: target = "10111"
Output: 3
Explanation: Initially, s = "00000".
Choose index i = 2: "00000" -> "00111"
Choose index i = 0: "00111" -> "11000"
Choose index i = 1: "11000" -> "10111"
We need at least 3 flip operations to form target.
Example 2:
Input: target = "101"
Output: 3
Explanation: Initially, s = "000".
Choose index i = 0: "000" -> "111"
Choose index i = 1: "111" -> "100"
Choose index i = 2: "100" -> "101"
We need at least 3 flip operations to form target.
Example 3:
Input: target = "00000"
Output: 0
Explanation: We do not need any operations since the initial s already equals target.
Constraints:
n == target.length1 <= n <= 100000(10^5)target[i]is either'0'or'1'.
문제 풀이 접근
금일 문제 풀이는 하면서 여러가지를 생각해봤다.
1. 1이 연속된 구간 섹션을 나누고 나눠진 갯수 출력하는 방식.
2. 주어진 문자열을 뒤부터 순환해서 마지막의 문자를 기억했다가 달라지는 인덱스를 삭제하는 방법
3. 앞에서부터 순환해서 다를때마다 카운트 올리고 출력하는 방식.
결국 위 3가지는 뭐 구간을 어떻게 나누고, 달라진것을 캐치하고 하는 방식에서 일단 명맥상 다 비슷하다.
틀린 코드도 결국 조금만 수정하면 다 풀릴 코드 였겠지만, 타임리밋은 조금 고민을 해봐야하긴한다.
인덱스 이하 좌측은 고려안해도 Remove 나, 새롭게 string 을 만드는 부분에서 뭔가 문제가 있는듯하다.
문제 풀이 플로우는 아래와 같다.
1. target에 1이 하나도 없다 == 즉 0으로 범벅이다. => 바꿀게 없다 0번 플립하면된다.
2. 내가 현재 기준이 될 문자열 하나를 선언한다. ( 문제에서 target.Length에 맞게 0으로 채운다했으니 초기에는 0으로 잡는다.)
3. 앞에서부터 인덱스를 넘겨가면서 내가 저장한 문자열과 다르면 내 기준 문자열을 변경하고 answer를 하나 올린다.
4. 끝까지 돌면 answer 반환하고 종료한다.
이 문제는 결국, 내가 쓰여진 것과 다르면 내 문자를 바꾸고 카운터 올리는 것이다. 플립 실제로 구현할 필요도 없다.
문제 풀면서 든 생각이지만 2차선 타다가 앞에 차를 만나서 1차선 갔다가 1차선에서 차를 또만나면 2차선 갔다가 이런 느낌으로 연산하면 이해가 편할것 같기도하다. 내가 2차선 -> 1차선 ( 플립 + 1) , 1차선 -> 2차선 ( 플립 +1 ) 하는 느낌을 받았기 때문이다.
실패한 코드 (Wrong Answer - 1번 방식)
public class Solution {
public int MinFlips(string target) {
// 10111
// 00111
// 11000
// 10111
string origin = string.Empty;
for(int i=0; i < target.Length;++i)
origin += 0;
int answer = 0;
if(origin == target)
return answer;
string[] seperate = target.Split('0');
answer = seperate.Length+1;
return answer;
}
}실패한 코드 (Time Limit Exceeded - 2번 방식)
public class Solution {
public int MinFlips(string target) {
// 10111
// 00111
// 11000
// 10111
string origin = string.Empty;
for(int i=0; i < target.Length;++i)
origin += 0;
int answer = 0;
if(origin == target)
return answer;
while(true)
{
if(origin == target)
return answer;
for(int i = 0; i < target.Length; ++i)
{
if(origin[i] == target[i]) continue;
filp(ref origin, i);
break;
}
++answer;
}
return answer;
}
public void filp(ref string target, int index)
{
for(int i = index; i < target.Length; ++i)
{
char character = target[i];
if(character == '0')
{
char[] charArr = target.ToCharArray(0,target.Length);
charArr[i] = '1';
target = new string(charArr);
}
else
{
char[] charArr = target.ToCharArray(0,target.Length);
charArr[i] = '0';
target = new string(charArr);
}
}
}
}정답 작성 코드 (C#)
public class Solution
{
public int MinFlips(string target)
{
int answer = 0;
if (target.Contains("1") == false)
return answer;
char nowChar = '0';
for(int i = 0; i < target.Length;++i)
{
if (target[i]!=nowChar)
{
nowChar = target[i];
++answer;
}
}
return answer;
}
}코드 결과
