백준 1439번 - 뒤집기 (C/C++)

 

 

 

 

무리 없이 풀었던 문제지만 뭔가..뭔가.. 내가 기존에 작성한 코드보다 더 나은 방법이 있을 것 같다.

그래서 다른 코드를 참고해보면서 개선점을 적어보기록 했다.

그리디 알고리즘을 이용한 문제다.

 

 

 

 

 

 

 

입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

 

 

쉽게 말해서 연속되는 숫자는 한꺼번에 뒤집을 수 있다는 가정 하에,

다솜이가 뒤집는 카운트의 최소 수는? 을 구하는 문제이다.

(이때 주의해야할 점은 0을 뒤집었을 때, 1을 뒤집었을 때 전체에 대한 가장 최소의 수를 찾는 것이다.)

 

 

 

 

---

 

 

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

int sum0 = 0;
int sum1 = 0;

void calculate(vector<string>& vec, int i)
{
	if (vec[i] == "0")
	{
		if (vec[i - 1] != "0") {sum0 += 1;}
	}
	else if (vec[i] == "1")
	{
		if (vec[i - 1] != "1") { sum1 += 1; }
	}
}

int main() {

	string S;
	cin >> S;
	vector<string> vec;

	for (char i : S) { vec.push_back(string(1, i)); }

	if (vec[0] == "0")
	{ sum0 += 1; }
	else sum1 += 1;

	for (int i = 1; i < vec.size(); i++) { calculate(vec, i); }

	if (sum0 > sum1) { cout << sum1; }
	else { cout << sum0; }
}

 

내가 제출한 코드는 이렇다.

calculate 함수는 sum의 숫자를 계산하는 숫자인데, 이를 0을 뒤집는 경우와 1을 뒤집는 경우로 분류하여 각각 계산하였다.

그리고 main 함수로 돌아와서 마지막에는 (0뒤경)과 (1뒤경)을 비교해서 더 작은 수를 출력하도록 코드를 짰다.

 

 

⬇️ 더 간소화된 코드 ⬇️

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

int main() {
    string S;
    int sum = 0; 
    cin >> S;

    for (int i = 0; i < S.size() - 1; i++) {
        if (S[i] != S[i + 1]) 
            sum++;
    }

    cout << (sum + 1) / 2 << endl;
}

 

 

⭐ 기존 코드와 차이점은 다음과 같다.

1. vector을 사용할 필요 없이 바로 string 변수 S 안에 입력받고, string을 그대로 비교해주었다.
2. 기존의 코드와는 다른 방식이 적용되었다.
( sum의 각각의 문자를 비교하며 0과 1의 변환이 나타나는 지점에 +1씩 카운트를 해주고,
 (sum+1)/2를 하는 계산 방법을 풀이 방식으로 사용하였다. 이게 가능한 이유가 뭘까?)

0->1이든 1->0이든 이들은 '하나의 그룹이 끝나는 지점'으로 이해할 수 있다. 따라서 이 지점을 +1로 카운트 해준다.
만약 000111000과 같은 수가 주어졌다면 변환 지점은 2, 그룹 개수는 3 (= 2+1)이 된다.
즉, 그룹의 개수는 변환지점 +1로 정의할 수 있다.

이때 답은 ( 전체 그룹 개수 / 2 )를 한 값이다.
왜 2로 나누어야 할까? 그룹은 단 두 개, 0 그룹과 1 그룹만 존재한다. 전환이 되면 0 다음에 1, 1 다음에 0이 올 것이다.  0그룹과 1그룹은 특성상 둘이 쭉 이어져 있을 것이고, 이때문에 전체 그룹 수에 2를 나누어 최소 뒤집기 그룹 수를 결정하는 것이다.