[백준알고리즘] 1439번: 뒤집기 -C++

[백준알고리즘] 1439번: 뒤집기 -C++

1439번: 뒤집기 (acmicpc.net)

1439번: 뒤집기

그리디 알고리즘을 풀어보고 싶어서, 안 푼 그리디 문제 중에 그나마 쉬운거부터 골랐다. 쉽게 풀긴 했는데, 이게 그리디인지는 느낌이 안 오는 문제였다. 다른 문제를 더 풀어봐야 할 것 같다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제풀이

0과 1로 이루어진 문자열이 주어진다. 이때 0은 1로, 1은 0으로 뒤집을 수 있다. 모두 같은 숫자로 이루어진 문자열을 만들기 위해서 최소로 뒤집는 횟수를 구하는 것이 문제다.

 

간단하게 문제를 풀었다. 연속된 같은 숫자를 한번에 뒤집을 수 있기 때문에, 0에서 1로 변하는 개수와 1에서 0으로 변하는 개수를 확인했다. 그래서 0에서 1로 바뀐 횟수와 1에서 0으로 바뀐 횟수의 최소 횟수를 출력했다.

단, 가장 처음에 시작하는 숫자는 이전에 0 또는 1의 상태가 없기 때문에, 해당 숫자로 변한 횟수를 직접 추가해야 한다.

 

즉, 0001100의 예제를 살펴보면, 0에서 1로 변한 횟수는 1번이며, 1에서 0으로 변한 값도 1번이다. 단, 0에서 시작했기 때문에 1에서 0으로 변한 횟수를 임의로 1번 더 추가해주었다.

따라서, 0에서 1로 변한 횟수는 1번, 1에서 0으로 변한 횟수는 2번으로 최소 횟수인 1이 나온다.

 

문제는 아래와 같은 코드로 통과했다.

#include <cstdio>
#include <iostream>
#include <string>

int main(void) {
	/* 입력 */
	std::string sNum;
	std::getline(std::cin, sNum);

	/* 변화 횟수 구하기 */
	unsigned int uiZeroCnt = 0; // 1이 시작한 횟수
	unsigned int uiOneCnt = 0; // 0이 시작한 횟수
	char cLatest = '\0';

	for ( std::string::iterator itNum = sNum.begin(); itNum != sNum.end(); ++itNum ) {
		if ( '\0' == cLatest ) {
			cLatest = *itNum;
			switch ( *itNum ) {
			case '0':
				uiZeroCnt++;
				break;

			case '1':
				uiOneCnt++;
				break;

			default:
				// error
				break;
			}
		}

		switch ( *itNum ) {
		case '0':
			if ( cLatest == *itNum ) {
				continue;
			}
			else {
				uiZeroCnt++;
				cLatest = '0';
			}
			break;

		case '1':
			if ( cLatest == *itNum ) {
				continue;
			}
			else {
				uiOneCnt++;
				cLatest = '1';
			}
			break;

		default:
			// error
			break;
		}
	}

	/* 출력 */
	printf("%d\n", (uiZeroCnt < uiOneCnt) ? uiZeroCnt : uiOneCnt);

	return 0;
}