[C] 백준 - 1439번: 뒤집기

8월 16일(수) -그리디 알고리즘(1439번)

1439번: 뒤집기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 입력은 char string[ 1,000,001 ] 에 문자열을 입력받는것으로 진행

- 기존에 존재하는 string에서는 0->1로 변하는 횟수를 변수 zero_to_one를 갱신하며 카운팅하고,

  복사한 copy_string에서는 1->0으로 변하는 횟수를 변수 one_to_zero를 갱신하며 카운팅해준다

- 출력은 zero_to_one과 one_to_zero 둘 중 더 작은 수를 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전

char string[1000001];

int main(void)
{
	scanf("%s", string);
	strcpy(copy_string, string);

	int zero_to_one = 0;
	int one_to_zero = 0;

	...

	return 0;
}

// 수정 후

char string[1000001];
char* copy_string;

int main(void)
{
	scanf("%s", string);
	copy_string = strdup(string);

	int zero_to_one = 0;
	int one_to_zero = 0;
	
    	...

	return 0;
}

1. 최초로 입력받는 문자열을 char string[ ]에 저장하고, strcpy를 통해서 copy_string에도 저장하고자 했음

-> 예제를 떠나서 출력자체가 제대로 나오지않음

-> 검색을 통해서 strdup 함수를 사용해서 문자열 복사를 진행

 

2. 추가로, strcpy 함수 사용시 CritisValidHeapPointer 에러가 발생했었음

-> strdpu함수를 사용하기위해 추가해놓았던 free(copy_string) 부분 때문에 문제가 발생했던듯

-> 해당 부분 삭제 후 정상적으로 풀이 가능

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(strcpy 함수 사용)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <string.h>

char string[1000001];
char copy_string[1000001];

int MIN(int x, int y)
{
	return ((x < y) ? (x) : (y));
}

int main(void)
{
	scanf("%s", string);
	strcpy(copy_string, string);

	int zero_to_one = 0;
	int one_to_zero = 0;
	for (int i = 0; string[i] != '\0'; i++)
	{
		if (string[i] == '0')
		{
			zero_to_one++;
			for (int j = i; string[j] && string[j] == '0'; j++)
			{
				string[j] = '1';
			}
		}
	}

	for (int i = 0; copy_string[i] != '\0'; i++)
	{
		if (copy_string[i] == '1')
		{
			one_to_zero++;
			for (int j = i; copy_string[j] && copy_string[j] == '1'; j++)
			{
				copy_string[j] = '0';
			}
		}
	}

	printf("%d", MIN(zero_to_one, one_to_zero));

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(strdup 함수 사용)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <string.h>

char string[1000001];
char* copy_string;

int MIN(int x, int y)
{
	return ((x < y) ? (x) : (y));
}

int main(void)
{
	scanf("%s", string);
	copy_string = strdup(string);

	int zero_to_one = 0;
	int one_to_zero = 0;
	for (int i = 0; string[i] != '\0'; i++)
	{
		if (string[i] == '0')
		{
			zero_to_one++;
			for (int j = i; string[j] && string[j] == '0'; j++)
			{
				string[j] = '1';
			}
		}
	}

	for (int i = 0; copy_string[i] != '\0'; i++)
	{
		if (copy_string[i] == '1')
		{
			one_to_zero++;
			for (int j = i; copy_string[j] && copy_string[j] == '1'; j++)
			{
				copy_string[j] = '0';
			}
		}
	}

	printf("%d", MIN(zero_to_one, one_to_zero));
	free(copy_string);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ