[프로그래머스] 수식 최대화 - LEVEL 2

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/67257

✍️ 문제 풀이

해당 문제는 단순 구현 문제로, 문자열 처리가 중점인 문제이다.

1) 입력받은 expression 문자열을 각 숫자와 연산자로 따로 나누어 저장한다.

• split() 함수 : 인수로 전달된 문자열을 숫자와 연산자로 나누어 같은 벡터에 순서대로 저장한다.
  • 문자열 내에서 '*', '+', '-' 를 각각 find 하여 그 인덱스(위치)가 가장 작은 연산자 (가장 앞에 있는 것)를 찾는다.
  • 해당 연산자를 기준으로 앞에 있는 문자열, 해당 연산자를 각각 result 벡터에 집어넣고, 기존 문자열을 연산자 뒤의 문자열로 교체한다.
  • 위 과정을 더 이상 연산자가 남지 않을 때까지 반복하고, 마지막 남은 문자열을 result 벡터에 집어넣고 result를 반환한다.
• 리스트 nums와 op를 선언하고, split() 함수에서 반환된 벡터를 확인하여 숫자 문자열은 nums에, 연산자는 op에 삽입한다.

2) 2차원 벡터 orders를 선언해 3개의 연산자로 만들 수 있는 우선순위 6개를 저장한다.

3) orders에 저장된 각각의 연산자 우선순위에 따라 주어진 문자열을 계산한다.

• nums와 op를 numsCopy, opCopy에 복사해 저장한다.
• 현재 순서 orders에 저장된 연산자들을 순서대로 적용하여 아래 과정을 반복한다.
  • opCopy에 저장된 각 연산자를 차례대로 확인한다.
    • 만약 해당 연산자가 orders의 현재 순서 연산자가 아니라면 다음 연산자로 넘어간다.
    • 현재 순서 연산자라면 opCopy의 끝 인덱스까지 확인할 때까지 아래 과정을 반복한다.
      • numsCopy에 저장된 해당 연산자의 앞과 뒤에 있는 숫자들을 해당 연산자로 계산해
        , 원래 numsCopy에 앞에 있는 숫자의 위치에 저장한다.
      • opCopy의 해당 연산자와, numsCopy의 뒤에 있는 숫자를 삭제한다.
        (리스트이므로 자동으로 당겨짐)
      • opCopy의 맨 앞으로 돌아간다.
    • opCopy의 끝까지 확인했다면 orders의 다음 순서 연산자로 넘어간다.
• 위 과정이 완료되면 numsCopy에 계산 완료된 숫자 하나만이 남는다. 이 숫자를 result 벡터에 삽입한다.

4) 6개의 우선순위를 각각 적용하여 계산된 값들이 최종적으로 result에 저장되고, 이 값들의 절대값들을 비교하여 가장 큰 값을 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <list>
using namespace std;

// 문자열을 각 연산자를 기준으로 나누어 숫자와 연산자로 저장
vector<string> split(string str)
{
	char dlim1 = '*', dlim2 = '+', dlim3 = '-';
	vector<string> result;
	int a, b, c;

	while (true)
	{
		a = find(str.begin(), str.end(), dlim1) - str.begin();
		b = find(str.begin(), str.end(), dlim2) - str.begin();
		c = find(str.begin(), str.end(), dlim3) - str.begin();

		if (a == str.size() && b == str.size() && c == str.size())
		{
			result.push_back(str);
			return result;
		}			
		else
		{
			int dlim = min({ a, b, c });
			result.push_back(str.substr(0, dlim));
			result.push_back(str.substr(dlim, 1));
			str = str.substr(dlim + 1, str.size() - dlim);
		}
	}
}

long long solution(string expression)
{
	// 연산자는 op, 숫자는 nums에 저장
	vector<string> v = split(expression);
	list<string> nums, op;
	for (int i = 0; i < v.size(); i++)
	{
		if (v[i] == "*" || v[i] == "+" || v[i] == "-")
			op.push_back(v[i]);
		else
			nums.push_back(v[i]);
	}

	vector<vector<string>> orders;
	orders.push_back({ "*", "+", "-" });
	orders.push_back({ "*", "-", "+" });
	orders.push_back({ "+", "*", "-" });
	orders.push_back({ "+", "-", "*" });
	orders.push_back({ "-", "+", "*" });
	orders.push_back({ "-", "*", "+" });

	vector<long long> result;
	for (int i = 0; i < orders.size(); i++)
	{
		list<string> numsCopy = nums, opCopy = op;
		for (int k = 0; k < 3; k++)
		{
			int j = 0;
			while(true)
			{
				if (j >= opCopy.size())
					break;

				auto it = opCopy.begin();				// 연산자 이터레이터
				advance(it, j);
				if (*it != orders[i][k])
				{
					j++;
					continue;
				}
					
				auto prevNumsIt = numsCopy.begin();		// 연산자 이전 글자 이터레이터
				auto postNumsIt = numsCopy.begin();		// 연산자 다음 글자 이터레이터
				advance(prevNumsIt, j);
				advance(postNumsIt, j + 1);

				if (*it == "*")
					*prevNumsIt = to_string(stoll(*prevNumsIt) * stoll(*postNumsIt));
				else if (*it == "+")
					*prevNumsIt = to_string(stoll(*prevNumsIt) + stoll(*postNumsIt));
				else
					*prevNumsIt = to_string(stoll(*prevNumsIt) - stoll(*postNumsIt));
				opCopy.erase(it);
				numsCopy.erase(postNumsIt);
				j = 0;
			}
		}
		result.push_back(stoll(*numsCopy.begin()));
	}

	long long maxValue = 0;
	for (int i = 0; i < result.size(); i++)
	{
		long long cur = llabs(result[i]);
		if (cur > maxValue)
			maxValue = cur;
	}
	return maxValue;
}