[BOJ] 백준 14888번 연산자 끼워넣기 C++(삼성 기출문제)

문제

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

14888번: 연산자 끼워넣기

삼성 코딩테스트 기출문제라고 한다. 백트래킹 문제인데 역시 삼성 문제답게 구현하기가 힘들었다.

다른 사람들 풀이를 안보고 풀려고 노력했더니 코드도 더러워지고 푸는데 2시간이나 걸렸다.

코드가 더러운만큼 다른 사람들의 풀이도 참고해보고 리팩토링할 생각이다.

풀이

첫번째로 4개의 연산자에 대해 입력을 받고 그 연산자들 전부를 (수열의 크기 - 1)만큼 순열을 돌려주었다.

하나의 순열이 생성되면 그 순열의 각각의 요소에 대해 oper라는 Queue에 넣어주고 calc 함수에서 연산자를 하나씩 Queue에서 빼면서 계산을 시키고 최종적으로 나온 값을 result 백터에 넣어주었다.

위의 프로세스를 만들어질 수 있는 모든 순열에 대해 진행시켜주면 된다.

그렇게 생성된 result 백터를 정렬하여 백터의 최댓값, 최솟값을 출력해주고 프로그램을 종료시켜주었다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<int> result;
char arr[12];
bool isused[12];
int sequence[12];
queue<char> oper;
vector<char> v;

void calc()
{
	int temp = 0;
	int idx = 2;
	bool init = true;

	while (!oper.empty())
	{
		char cur = oper.front();

		if (init)
		{
			if (cur == 'a')
			{
				temp = sequence[0] + sequence[1];
			}
			else if (cur == 's')
			{
				temp = sequence[0] - sequence[1];
			}
			else if (cur == 'm')
			{
				temp = sequence[0] * sequence[1];
			}
			else if (cur == 'd')
			{
				temp = sequence[0] / sequence[1];
			}

			init = false;
		}
		else
		{
			if (cur == 'a')
			{
				temp += sequence[idx];
			}
			else if (cur == 's')
			{
				temp -= sequence[idx];
			}
			else if (cur == 'm')
			{
				temp *= sequence[idx];
			}
			else if (cur == 'd')
			{
				temp /= sequence[idx];
			}

			idx++;
		}
		oper.pop();
	}

	result.push_back(temp);
}

void func(int k)
{
	if (k == n - 1)
	{
		for (int i = 0; i < v.size(); i++)
		{
			oper.push(arr[i]);
		}
		calc();
		return;
	}

	for (int i = 0; i < v.size(); i++)
	{
		if (!isused[i])
		{
			isused[i] = true;
			arr[k] = v[i];
			func(k + 1);
			isused[i] = false;
		}
	}
}

void makeVec()
{
	int a = 0; int s = 0; int m = 0; int d = 0;
	cin >> a >> s >> m >> d;

	for (int i = 0; i < a; i++)
	{
		v.push_back('a');
	}
	for (int i = 0; i < s; i++)
	{
		v.push_back('s');
	}
	for (int i = 0; i < m; i++)
	{
		v.push_back('m');
	}
	for (int i = 0; i < d; i++)
	{
		v.push_back('d');
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> sequence[i];
	}

	makeVec();

	func(0);

	sort(result.begin(), result.end());

	cout << result[result.size() - 1] << "\n" << result[0];
}