[BOJ]1439뒤집기 : 그리디 알고리즘 C++ 해결 및 설명

 

 

---

문제 해결 알고리즘

1. list에 입력한 바이너리 문자열을 넣는다.

2. 0과 1중 무엇을 뒤집을 지 결정하는 잣대로 연속된 1과 0의 개수를 세도록 한다. 

3. 어떻게 연속된 1과 0의 개수를 세느냐

- for문에서 list[i]와 list[i+1]의 변화가 있으면 count, 없으면 넘어가도록

- 0과 1을 구분하기 위해 cnt0, cnt1 변수를 따로 저장하고, list[i+1]이 0이면 cnt0++,  1이면 cnt1++를 실행한다. 

4. cnt1와 cnt0중에 적은 것을 출력한다. 

 

#include <iostream>
#include <string>
using namespace std;



int main()
{
	int cnt1, cnt0;
	char s[1000000];
	cin >> s;
	if (s[0] == '1')
	{
		cnt1 = 1;
		cnt0 = 0;
	}
	else
	{
		cnt0 = 1;
		cnt1 = 0;
	}
	int i = 0;
	while (s[i] != NULL)
	{
		if (s[i] == s[i + 1])
		{
			i++;
			continue;
		}
		else
		{
			if (s[i + 1] == '0')
				cnt0++;
			else
				cnt1++;
		}
		i++;
	}

	if (cnt1 >= cnt0)
		cout << cnt0 << endl;
	else
		cout << cnt1 << endl;

	return 0;
}

맨 처음 제출한 코드. 0000000을 입력하면 1이 뜨는 문제를 확인할 수 있었다. 

#include <iostream>
#include <string>
using namespace std;



int main()
{
	int cnt1 = 0, cnt0 = 0;
	char s[1000000];
	cin >> s;
	/*
	if (s[0] == '1')
	{
		cnt1 = 1;
		cnt0 = 0;
	}
	else
	{
		cnt0 = 1;
		cnt1 = 0;
	}
	*/

	int i = 0;
	while (s[i] != NULL)
	{
		if (s[i] == s[i + 1])
		{
			i++;
			continue;
		}
		else
		{
			if (s[i + 1] == '0')
				cnt0++;
			else
				cnt1++;
		}
		i++;
	}

	if (cnt1 >= cnt0)
		cout << cnt0 << endl;
	else
		cout << cnt1 << endl;

	return 0;
}

 

그래서 다음과 같이 맨 처음 바이너리에 따라 변수 세팅을 해주는 코드를 지웠는데, 000000을 입력하였을 때 0이 뜨긴 하나 while문의 조건에서 i번째까지 NULL임을 판단하니 리스트의 마지막 부분과 그 다음부분(NULL)값이 일치하지 않아 카운트가 한번더 추가되는 버그가 발생했다. 

 

<최종 해결 코드>

#include <iostream>
using namespace std;

int main()
{
	int cnt1 = 0, cnt0 = 0;
	char s[1000000];
	cin >> s;

	if (s[0] == '1')
		cnt1++;
	else
		cnt0++;

	int i = 0;
	while (s[i+1] != NULL)
	{
		if (s[i] == s[i + 1])
		{
			i++;
			continue;
		}
		else
		{
			if (s[i + 1] == '0')
				cnt0++;
			else
				cnt1++;
		}
		i++;
	}

	if (cnt1 >= cnt0)
		cout << cnt0 << endl;
	else
		cout << cnt1 << endl;

	return 0;
}