[C#] 백준 1439 뒤집기

[ 문제 ]

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오

 

[ 코드 ]

1. 내 코드(1)

- 중복되는 숫자를 지우고 0과 1을 카운트해서 최솟값 출력

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

string s = sr.ReadLine();
char c = s[0];
string removeS = c.ToString();
int countO = 0;
int countZ = 0;

for (int i = 1; i < s.Length; i++)
{
    if (c != s[i])
    {
        removeS += s[i];
        c = s[i];
    }
}

for (int i = 0; i < removeS.Length; i++)
{
    if (removeS[i] == '1') countO++;
    else countZ++;
}

sw.Write(countZ > countO? countO : countZ);
sw.Flush();
sw.Close();
sr.Close();

 

2. 내 코드(2)

- for문 하나만으로 최솟값 출력

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

string s = sr.ReadLine();
char c = s[0];
string removeS = c.ToString();
int countO = 0;
int countZ = 0;
int j = 1;

if (removeS[0] == '1') countO++;
else countZ++;

for (int i = 1; i < s.Length; i++)
{
    if (c != s[i])
    {
        removeS += s[i];
        if (removeS[j] == '1') countO++;
        else countZ++;
        j++;
        c = s[i];
    }
}

sw.Write(countZ > countO ? countO : countZ);
sw.Flush();
sw.Close();
sr.Close();

 

3. 다른 사람 코드 참고

- 현재 값과 이전 값이 다른 경우 2가지를 배열에 저장해서 배열끼리 비교

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

string s = sr.ReadLine();
sw.Write(minCount(s));

string minCount(string s)
{
    int[] arr = new int[2];
    int index = 0;
    char temp = s[0];

    for(int i = 0; i < s.Length; i++)
    {
        if (s[i] != temp)
        {
            arr[index]++;
            temp = s[i];
            index = (index + 1) % 2;
        }
    }
    arr[index]++;

    return arr[0] >= arr[1] ? arr[1].ToString() : arr[0].ToString();
}

sw.Flush();
sw.Close();
sr.Close();

 

세번째 코드가 메모리도 시간도 빠르다. 굳이 for문을 이용해 새 배열을 만들지않고 값을 비교하는것이라 그런 것 같다.

 

[ 실행화면 ]

case: 1

case: 2

case: 3

case: 4

case: 5

 

 

 

 

---

문제링크: https://www.acmicpc.net/problem/1439

1439번: 뒤집기