[C] 백준 - 1541번: 잃어버린 괄호

4월 4일(화) - 그리디 알고리즘(1541번)

1541번: 잃어버린 괄호

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

 

최초 생각 정리

- 최대 50개의 입력은 문자열로 입력받는다

- 괄호를 적당히 쳐서 식의 값을 최솟값으로 만들어야하기 때문에,

  -가 처음나오고나면, 다시 -가 나오기전까지 그 사이에서 +를 통해 최대한 큰 값을 만들어서 뺄셈을 진행해야한다

- 즉, 처음 - 가 나오면 괄호를 열면서 - 바로 뒤의 숫자를 최대한 큰 값으로 부풀린다

  그리고 새로운 - 가 나오거나 or 문자열이 종료되는 경우에 괄호를 닫는다

- 따라서 strlen을 활용해서 반목문을 돌리며

  if -> 문자열로 -를 입력받은 경우

  else if -> 문자열로 +를 입력받은 경우

  else -> +,- 모두 아닌 일반 숫자를 입력받은 경우

  이렇게 나누어서 진행한다

for (int i = 0; i < len; i++)
	{
		// - 나온 순간
		// 괄호시작-> 바로 뒤의 숫자부터
		// 괄호종료-> 새로운 - 나오거나 아니면 string이 끝나는 경우

		if (string[i] == '-')
		{
			if (string[i] == '\0')
			{
            
			}
		}
		else if (string[i] == '+')
		{
			
		}
		else
		{
        
		}
	}

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

 

문제점

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int main(void)
{
	char string[51];
	scanf("%s", string);

	int tmp_plus = 0;
	int sum = 0;
	int len = strlen(string);
	for (int i = 0; i < len; i++)
	{
		if (string[i] == '-')
		{
			if (string[i] == '\0')
			{
				sum = sum + tmp_plus;
			}
			tmp_plus = 0;
		}
		else if (string[i] == '+')
		{
			sum = sum + tmp_plus;
			tmp_plus = 0;
		}
		else
		{
			tmp_plus = tmp_plus + (string[i] - '0');
		}
	}

	printf("%d", sum);
	return 0;
}

1. 예제 1 입력시 -> 5 / 예제 2 입력시 -> 6이 출력되고 있음

-> +나-가 아닌 숫자가 연속으로 입력되는 경우 else 부분에서 숫자가 잘못 저장되고 있는 듯함

-> tmp_plus = tmp_plus * 10 부분을 추가하면서 숫자의 자릿수 증가에 따른 값 변화를 구현함

 

2. 다시보다보니 첫번째 if에서 -인 경우와 \0인 경우를 동시에 표현하는게 나을듯함

-> or 표현으로 묶어줌

 

	for (...)
	{
		if (string[i] == '-' || string[i] == '\0')
		{
			sum = sum + tmp_plus;
			tmp_plus = 0;

			arr[j] = sum;
			j++;
			sum = 0;
		}
		else if (string[i] == '+')
		{
			...
		}
		else
		{
			...
		}
	}

	int result = arr[0];
	for (int i = 1; i < j; i++)
	{
		result = result - arr[i];
	}

3. - 이후에 +를 입력받게되눈 경우, 최대한 큰 값으로 뿔려서 -계산을 크게 진행하기 위한 부분이 계속 튕김

-> 풀이참조  https://henrynoh.tistory.com/20

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

 

풀이

(풀이참고 -> https://henrynoh.tistory.com/20)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int main(void)
{
	char string[51];
	scanf("%s", string);

	int arr[51] = { 0, };
	int j = 0;
	int tmp_plus = 0;
	int sum = 0;
	int len = strlen(string);
	for (int i = 0; i <= len; i++)
	{
		if (string[i] == '-' || string[i] == '\0')
		{
			sum = sum + tmp_plus;
			tmp_plus = 0;

			arr[j] = sum;
			j++;
			sum = 0;
		}
		else if (string[i] == '+')
		{
			sum = sum + tmp_plus;		
			tmp_plus = 0;
		}
		else
		{
			tmp_plus = tmp_plus * 10;
			tmp_plus = tmp_plus + (string[i] - '0');
		}
	}

	int result = arr[0];
	for (int i = 1; i < j; i++)
	{
		result = result - arr[i];
	}

	printf("%d", result);
	return 0;
}

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