[Beakjoon Online Judge] 1541 - 잃어버린 괄호(C++)

I 문제 소개

---

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

입력

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

 

출력

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

---

II 문제 풀이

---

지난번 '동전0' 문제에 이어서 탐욕법(그리디 알고리즘)을 사용하는 문제이다.

동전은 가장 큰 단위의 화폐부터 내는게 핵심이었다면, 이 문제에 탐욕법을 적용하는 핵심은, 더하기부터 하는 것이다.

 

왜냐하면 가장 작은 수를 만들기 위해서는 가장 크게 빼줘야하는데, 가장 크게 만드려면 더하기를 먼저 다 해주면 되기 때문이다.

 

0. 초기 환경 설정

---

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(void)
{
	vector<int> num;
	vector<int> operater; //1:plus 2:minus
	
	string stemp; // string temp
	string str;
	
	int i,temp,answer,sw;
    
	cin >> str; // input
    
	/* operation */
    
	cout << answer; // output
	return 0;
}

우선 "55-50+40"같은 문자열 입력이 들어왔을 때 55 / - / 50 / + / 40으로 나눠야했다.

55, 50, 40을 보관할 벡터 num과, +와 -를 보관할 벡터 operater을 만들었다. 다만 operater은 '+'도 연산자로 바로 기능하는게 아니라 char형식이기 때문에 그럴 바에 int 벡터로 1이면 +, 2면 -로 구분하게 만들 예정이다.

 

사실 한 벡터에 다 넣어도 됐는데 그러면 나중에 생각하기 불편해서 일단 따로 만들었다.

 

TMI로 연산자를 영어로 하면 operator지만 이는 이미 연산자 함수가 존재하기 때문에 벡터 이름을 operator로 선언할 수 없어서 operater이라고 적어봤다.

 

 

1. 문자열 나누기

---

temp = 0;
sw = 0;
for(i=0;i<str.size();i++)
{
	if(str[i]=='+'||str[i]=='-')
	{
		if(str[i]=='+')
			operater.push_back(1);
		else
			operater.push_back(2);
		stemp = str.substr(temp, i - temp);
		num.push_back(stoi(stemp));
		temp = i+1;
		sw = 1;
	}
}

for(i=str.size()-1;;i--)
{
	if(str[i]=='+'||str[i]=='-')
	{
		stemp = str.substr(temp, i + temp);
		num.push_back(stoi(stemp));
		break;
	}
}

문자열을 앞에서부터 읽다가 연산자에 도착하면 그 앞까지의 문자열을 substr로 자르고, stoi로 int로 변환하여 num에 넣어준다.

그리고 operater에 +는 1을, -는 2를 넣어준다.

 

temp의 역할은 앞에서 숫자와 연산자를 각각 추가했으면 다시 처음부터 문자열을 자르면 안되고, 추가했던 연산자 뒤부터 잘라야하기 때문에 그 위치를 저장해주는 역할을 수행한다. i일 때는 연산자에 도착한 시점이므로, 숫자에 들어가면 안되니까 i+1을 저장해준다.

 

sw는 예외처리하려고 넣은 변수인데, 밑에서 설명하겠다.

 

그리고 밑에 있는 for문은, 만약 1+2-6이라는 문자열이 들어오면 연산자 기준으로 저장하는 위 for문에서는 1 + 2 - 까지만 저장을 하기 때문에 마지막 숫자인 6을 넣기 위해 거꾸로 한 번 탐색해줬다.

 

input : "55-50+40"
num : { 55, 50, 40 }
operater : { 2, 1 }

 

2. 덧셈부터 처리

---

for(i=0;i<operater.size();)
{
	if(operater[i]==1)
	{
		num[i] = num[i] + num[i+1];
		num.erase(num.begin()+i+1);
		operater.erase(operater.begin()+i);
	}
	else if(operater[i]==2)
		i++;
}

덧셈을 처리하는 과정은, 앞에서부터 탐색하면서 첫번째 항에 둘의 합을 저장하고 두번째 항은 삭제하는 방식을 사용해 한바퀴만 돌아도 덧셈은 모두 수행되게 하였다.

erase를 사용해 벡터의 원소 하나가 지워지면 한칸씩 자동으로 당겨지기 때문에 i를 따로 더하거나 하지 않아도 알아서 넘어간다. 다만 덧셈만 계산하는 중이므로 아무것도 동작안하게 할 뺄셈이 들어오면 i를 한 개 늘려서 다음으로 넘어가 줘야 했다.

 

num : { 55, 90 } // 40 삭제
operater : { 2 ) // 1 삭제

 

3. 뺄셈(최종 계산)

---

문제에서 덧셈과 뺄셈밖에 주지 않으므로 2단계를 거친 상태라면 뺄셈만 남게 된다. 따라서 첫항에서 모든 항을 빼주면 그것이 이 문제의 답이 된다.

이 말을 코드로 옮기면 다음과 같다.

answer = 0;
for(i=0;i<num.size();i++)
{
	if(i==0)
		answer += num[i];
	else
		answer -= num[i];
}

 

* 예외 처리

---

이대로 백준에 제출했는데, 채점이 한 70%까지 진행되다가 틀렸습니다나 시간 초과 메모리 초과가 아닌 런타임 에러가 떠서 반례를 찾아야했다.

 

한참 반례를 찾다가 허탈하게도 내 코드는 연산자를 기준으로 계산하기 때문에 숫자 하나만 입력했을 때에는 operater에 원소가 하나도 없으므로 런타임 에러가 발생하는 것이었다.

 

그래서 1단계에서 sw를 만들어 놓았고, 아래와 같은 코드를 추가했다.

 

if (sw == 0)
{
	cout << str;
	return 0;
}

너무 짜증이 났던 나머지 그냥 예외가 되면 바로 return 0가 되게 했다.

확실한 상황이 아니면, 확실한 상황이더라도 웬만하면 이렇게 쓰면 안되지만 그냥 이렇게 썼다.

 

만약 처음부터 이걸 인지하고 있었다면 이렇게 쓰지 않고 if - else로 썼을텐데 말이다.

 

4. 최종

---

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(void)
{
	vector<int> num;
	vector<int> operater; //1:plus 2:minus
	
	string stemp;
	string str;
    
    int i,temp,answer,sw;
    
	cin >> str;
	
	temp = 0;
	sw = 0;
	for(i=0;i<str.size();i++)
	{
		if(str[i]=='+'||str[i]=='-')
		{
			if(str[i]=='+')
				operater.push_back(1);
			else
				operater.push_back(2);
			stemp = str.substr(temp, i - temp);
			num.push_back(stoi(stemp));
			temp = i+1;
			sw = 1;
		}
	}

	if (sw == 0) // exception : input only one
	{
		cout << str;
		return 0;
	}

	for(i=str.size()-1;;i--)
	{
		if(str[i]=='+'||str[i]=='-')
		{
			stemp = str.substr(temp, i + temp);
			num.push_back(stoi(stemp));
			break;
		}
	}

	for(i=0;i<operater.size();)
	{
		if(operater[i]==1)
		{
			num[i] = num[i] + num[i+1];
			num.erase(num.begin()+i+1);
			operater.erase(operater.begin()+i);
		}
		else if(operater[i]==2)
			i++;
	}

	answer = 0;
	for(i=0;i<num.size();i++)
	{
		if(i==0)
			answer += num[i];
		else
			answer -= num[i];
	}
	
	cout << answer;
	return 0;
}

 

III 느낀점

---

동전 문제는 명확하게 가장 이득인 선택을 할 수 있었는데, 이 문제는 어떻게 풀어야할지 감을 잡는 데 살짝 걸렸다.

사실은 탐욕법과는 거리가 멀고 수학적으로 접근해서 푼 것 같다.

 

실제로 탐욕법은 항상 최선일 수 없으며, 최선이었는지 확인하는 과정도 들어가야하는데, 이 문제에서 나는 가장 최선인 방법을 찾았고 따로 확인하지도 않았다.

 

또한 중간에 예외처리를 하지 못한 것도 좀 더 꼼꼼할 수 있었는데 그러지 못했다.

 

탐욕법은 좀 더 공부를 해야할 것 같다!

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 1541번 잃어버린 괄호 C++

BOJ 1541번 잃어버린 괄호 C++

백준 1541번 잃어버린 괄호 C++