백준[2504] 괄호의 값

아이디어

• [stack]을 사용할 줄 알아야한다.
• 문자열을 숫자로 바꾸는 발상의 전환이 필요하다

접근방식

• stack을 생성해서 올바른 괄호인지 검사한다.
  1. 첫 시작이 닫힌 괄호면 잘못된 괄호로 판단한다.
  2. 괄호를 검사하면서 각 괄호를 숫자로 변경하여 새로운 문자열에 넣어준다 (저는 '[' = -11, ']' = -10, '(' = -2, ')' = -1로 두었습니다.)
  3. [stack의 top]과 [넣으려는 괄호]가 올바르게 닫히는 괄호면 pop해준다. (중요!)
  4. 만약 stack이 비어있지 않다면 올바르지 않은 괄호 요소가 남아있다는 것이므로 0을 print해주고 종료한다.

• 올바른 괄호라는 것을 확정, 함수를 사용해서 괄호를 점차 줄여준다.
  1. i번째, i+1번째 요소가 바로 열리고 닫히는 괄호면 숫자로 판단, 구간을 해당하는 숫자로 바꿔주고 다시 함수를 실행한다.
  2. i번째, i+1번째 요소가 양수라면 둘다 숫자로 판단, 두 숫자를 더해주고 함수를 실행한다
  3. i+1번째 요소가 숫자이고, 양 옆 요소가 올바른 괄호라면 곱셈을 실행하고 함수를 실행한다.
  4. 지속적으로 괄호를 줄이다보면 벡터의 크기가 1이 된다. 이는 최종적으로 계산이 끝난 숫자를 뜻하므로 출력 후 종료한다.

vector<int> int_gwalho;

void make_answer()
{
	if (int_gwalho.size() == 1)
	{
		printf("%d", int_gwalho.front());
		return;
	}


	for (int i = 0; i < int_gwalho.size()-1; i++)
	{
		if (int_gwalho[i] == -2 && int_gwalho[i + 1] == -1)
		{
			int_gwalho[i] = 2;
			int_gwalho.erase(int_gwalho.begin() + i + 1);
			break;
		}
		else if (int_gwalho[i] == -11 && int_gwalho[i + 1] == -10)
		{
			int_gwalho[i] = 3;
			int_gwalho.erase(int_gwalho.begin() + i + 1);
			break;
		}
		else if (int_gwalho[i] > 0 && int_gwalho[i + 1] > 0)
		{
			int_gwalho[i] = int_gwalho[i] + int_gwalho[i + 1];
			int_gwalho.erase(int_gwalho.begin() + i + 1);
			break;
		}
		else if (int_gwalho[i] == -2 && int_gwalho[i + 1] > 0 && int_gwalho[i + 2] == -1)
		{
			int_gwalho[i] = int_gwalho[i + 1] * 2;
			int_gwalho.erase(int_gwalho.begin() + i + 1,int_gwalho.begin()+i+3);
			break;
		}
		else if (int_gwalho[i] == -11 && int_gwalho[i + 1] > 0 && int_gwalho[i + 2] == -10)
		{
			int_gwalho[i] = int_gwalho[i + 1] * 3;
			int_gwalho.erase(int_gwalho.begin() + i + 1, int_gwalho.begin() + i + 3);
			break;
		}
	}

	make_answer();
}

int main()
{
	string gwalho;

	cin >> gwalho;

	if (gwalho.front() == ')' || gwalho.front() == ']')
	{
		printf("0");
		return 0;
	}

	stack<char> check;

	for (int i=0; i<gwalho.size();i++)
	{
		char c = gwalho[i];

		if (c == '[') int_gwalho.push_back(-11);
		else if (c == ']') int_gwalho.push_back(-10);
		else if (c == '(') int_gwalho.push_back(-2);
		else int_gwalho.push_back(-1);

		if (check.empty()) check.push(c);

		else if (check.top() == '[' && c == ']') check.pop();

		else if (check.top() == '(' && c == ')') check.pop();

		else check.push(c);
	}

	if (!check.empty())
	{
		printf("0");
		return 0;
	}

	make_answer();

	return 0;
}

평가

쉬워보였지만, 덧셈에서 막혀 6시간 정도 걸린 문제. 생각을 많이 해야하는 문제.

저는 이미 stack을 사용해서 올바른 괄호인지를 판단하는 문제(백준 9012 : 괄호)를 풀어봤기 때문에 stack을 사용해야 한다는 것은 인지하고 있었습니다.
그러나, 덧셈을 어떻게 처리해야 할지 몰라 stack으로 이리 저리 처리하다, stack은 올바른 괄호인지 검사하는 용도로만 사용하였습니다.

하지만, 괄호와 숫자를 섞어 사용하기에 어려움을 겪었습니다.
그래서 괄호를 숫자로 사용한다는 아이디어가 떠올라, 괄호 문자열을 숫자열로 바꾸어 함수를 사용하여 문제 해결을 하였습니다.

풀면서도 '이렇게 푸는건 너무 비효율적일 것 같은데'라고 생각되는 풀이였습니다. 다른 분들의 풀이에서 얻은 아이디어는 '분배법칙' 이었습니다. 굳이 안쪽에서 더하고 곱하지 않고, 분배를 통해 각각 곱셈들을 나눠서 한꺼번에 차례씩 더하는 아이디어였습니다.