[C언어] 백준 1541 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1 

55-50+40

예제 출력 1 

-35

예제 입력 2 

10+20+30+40

예제 출력 2 

100

예제 입력 3 

00009-00009

예제 출력 3 

0

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

연산 문자열을 입력받고 결과값을 최소로 만드는 문제입니다.

즉 - 부호가 들어 왔을 때 다음 -부호가 들어오기 전까지 모든 연산을 -로 하라는 문제이죠

+와 -를 구분해서 최소값을 만들기 때문에 그리디 알고리즘으로 분류할 수도 있겠네요.

55-50+40

예제 입력 1입니다.

위와 같이 들어온 경우 연산을

55-(50+40)

이런식으로 바꾸라는 문제인데요

생각보다 간단합니다 위에서 말씀 드렸듯 -부호가 들어왔을 때

다음 -부호가 들어오기 전까지 모든 연산을 -로 하면 됩니다.

 

 

 

반응형

전체 코드

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

char	str[51], *temp;
int	result = 0, i = 0, f, len;

void	oper()
{
	// + 또는 - 부호가 들어왔을때
	if (str[i] == '+' || str[i] == '-')
	{
    	// - 부호인 경우 모든 연산을 -로 처리
		if (str[i] == '-')
			f = -1;
		i++;
	}
	len = 0;
    // 정수 문자열 길이 재기
	for (; str[i] && '0' <= str[i] && str[i] <= '9'; i++)
		len++;
	temp = (char *)malloc(sizeof(char) * len + 1);
	strncpy(temp, &str[i - len], len + 1);
	temp[len] = '\0';
	result += f * atoi(temp);
	free(temp);
}

int	main(void)
{
	scanf("%s", str);
	for(; str[i]; i++)
	{
		f = 1;
		while (str[i])
			oper();
	}
	printf("%d\n", result);
}

str 문자열을 입력받고 str의 인덱스가 NULL일 때까지 반복해줍니다.

oper 함수에서 연산자가 들어왔을 때 따로 처리를 해주었는데요

+인 경우는 인덱스만 옮기고 -인 경우는 따로 플래그를 세워 모든 연산을 뺄셈 처리했습니다.

이후 정수 문자열의 길이를 재준뒤 malloc으로 동적할당 하고 strncpy함수를 이용해

정수 문자열 길이만큼 복사를 해준뒤 atoi 함수로 문자열을 정수로 바꿔서 플래그값과 같이 연산해 값을 초기화 해줍니다.

 

42서울 하면서 꽤나 많이 본 문제처럼 느껴졌는지 생각보다 쉽게 풀었네요.