△ - [ 그리디 ] 03 문자열 뒤집기 - R

난이도 : 하  풀이시간 : 30/15  시간제한 : 2초  기출 : 핵심 유형

[ 그리디 ] 03 문자열 뒤집기

 

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게

 

만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다.

 

뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다. 예를 들어 S = 0001100일 때는 다음과 같습니다.

 

1. 전체를 뒤집으면 1110011이 됩니다.

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

 

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두

 

같은 숫자로 만들 수 있습니다.

 

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

 

:: 입력 조건

 

첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다. S의 길이는 100만보다 작습니다.

 

:: 출력 조건

 

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

 

---

  아이디어  

1. 문자열 입력받기

2. 문자열을 모두 0으로 바꾸는 경우의 수와 모두 1로 바꾸는 경우의 수를 모두 체크

    i ) 만약 현재 검사하는 자리의 숫자가 0이고 그 다음 자리 숫자가 1 이라면 

       0으로 바꾸는 경우의 수와 1로 바꾸는 경우의 수를 모두 하나씩 증가시킴

   ii ) 반대로 현재 검사하는 자리의 숫자가 1이고 그 다음 자리 숫자가 0 이라면

      0으로 바꾸는 경우의 수를 증가시킴

쓰다보니까 틀렸네 다시 생각해봄

 

다시 생각한 결과

   i ) 문자열의 첫 수를 확인해서 0인 경우 1로 바꾸는 경우의 수를 하나 증가시키고 1인 경우 0으로 바꾸는 경우의 수를 하나 증가시킴

  ii ) 그리고 조건문은

0->1 일 때 0으로 바꾸는 경우의 수 증가

1->0 일 때 1로 바꾸는 경우의 수 증가

이렇게 적어야 함

 

처음 방법으로 했을 때 결과가 다 맞게 나와서 아이디어 정리를 안했으면 몰랐을 듯 !

큰 일 날 뻔 ㅎ

 

  내   코드   // 틀렸는데 알아서 고침  

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

int main() {

	string s;
	cin >> s;

	int cnt0 = 0, cnt1 = 0; 
	// cnt0 = 모든 수를 0으로 바꾸는 경우 , cnt1 = 모든 수를 1로 바꾸는 경우

	if (s[0] - '0' == 0) { cnt1++; }
	else cnt0++;

	for (int i = 1; i < s.length()-1; i++) {
		int first = s[i] - '0';
		int second = s[i + 1] - '0';
		if (first == 0 && second == 1) {
			cnt0++;
		}
		else if (first == 1 && second == 0) {
			cnt1++;
		}
	}

	if (cnt0 < cnt1) cout << cnt0;
	else cout << cnt1;

}

 

 

  정답  코드  

#include <bits/stdc++.h>

using namespace std;

string str;
int count0 = 0; // 전부 0으로 바꾸는 경우
int count1 = 0; // 전부 1로 바꾸는 경우

int main(void) {
    cin >> str;

    // 첫 번째 원소에 대해서 처리
    if (str[0] == '1') {
        count0 += 1;
    }
    else {
        count1 += 1;
    }

    // 두 번째 원소부터 모든 원소를 확인하며
    for (int i = 0; i < str.size() - 1; i++) {
        if (str[i] != str[i + 1]) {
            // 다음 수에서 1로 바뀌는 경우
            if (str[i + 1] == '1') count0 += 1;
            // 다음 수에서 0으로 바뀌는 경우
            else count1 += 1;
        }
    }

    cout << min(count0, count1) << '\n';
}

 

  리뷰  

처음에 0으로 바꾸는 경우와 1로 바꾸는 경우를 모두 구해서 비교해야한다는 게 생각나서

2회차 하는 보람이 있네 싶었는데 ,,, 

정작 푸는 로직은 한 번 틀림

바보녀석 

그래도 이제 안 틀리면 되니까 괜찮음 ㅇㅇ