[코딩테스트 C++] 뒤집기

오늘의 문제

뒤집기

접근방식

• 1로 다 뒤집어본 결과, 0으로 다 뒤집어 본 결과에서 더 작은것을 출력한다.
• 이전에 2차원 배열로 된 다른 문제를 풀어봤던 경험으로 바로 풀 수 있었다.
• 처음 상태에서 뒤집는 경우가 왜 가장 적은 경우인가 하면, 양쪽을 가운데에 맞춰 바꾼 후에 다시 뒤집는 것 보다 양쪽을 가운데에 맞추고 끝내는 것이 반드시 작은 결과가 나오기 때문.
• 그렇기에 문제가 단순해진다.

나의 풀이

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

int solution(){
    int one=0;
    int zero = 0;
    for(int i=0;i<s.size();i++){
        if(s[i] == '0'){
            one++;
            while(s[i]== '0')
                i++;
        }
    }
    for(int i=0;i<s.size();i++){
        if(s[i] == '1'){
            zero++;
            while(s[i]== '1')
                i++;
        }
    }
    return min(one, zero);
}

다른 풀이

#include <cstdio>
using namespace std;

int main(){
	int prev = -1, cur, cnt = 1;
	while(scanf("%1d", &cur) > 0){
		if(prev != -1 && prev != cur) cnt++;
		prev = cur;
	}
	printf("%d\n", cnt/2);
}

배울점

• 그냥 앞이랑 다르면 더하는것으로 구할 수 있다!
• 와 그 중간에 끼어있는 값이 전체 바뀐 횟수의 1/2이라는 걸 이용했다. 대단