[알고리즘] 수식 최대화 (2020 카카오 인턴십)

코딩테스트 연습 - 수식 최대화

 상반기 카카오 인턴십 때 나온 문제이다. 해당 코딩 테스트에 참가했었기에 기억이 난다. (통과는 못했다.)

 이 문제도 결국 못 풀었던 걸로 기억한다. 지금와서 다시 찬찬히 살펴보니 결국 문자열 처리 문제이다. 정확히 말하자면 '브루트 포스 + 문자열 처리' 문제라고 할 수 있겠다.

 

 브루트 포스 문제인만큼 재귀 함수 사용은 필수적이다. 모듈은 크게 2개로 나누었는데 첫 번째는 '연산자 우선순위 결정' 메서드이고 나머지 하나는 '수식 계산' 메서드이다.

 

---

연산자 우선순위 결정 메서드

	//모든 연산자 우선순위 경우의 수 만들기
	static void recursive(int depth, int op_index, String expression, String[] operators)
	{
		if(depth == 3)
		{
			long result = calculate(expression, 0, operators);

			max = Math.max(max, Math.abs(result));
		}
		else
		{
			for(int i = 0;i < op_list.length;i++)
			{
				if(!visited[i])
				{
					visited[i] = true;
					operators[op_index] = op_list[i];
					recursive(depth+1, op_index+1, expression, operators);
					visited[i] = false;
				}
			}
		}
	}

 depth가 3 미만일 때는 연선자들을 우선순위별로 저장하고 있는 operators 배열을 만들고 depth가 3이 되서 완전히 우선순위가 결정되면 해당 우선순위에 따라 수식을 계산한다. 그리고 계산한 수식의 결과의 절대값 중 최대값을 max에 저장한다.

 

---

수식 계산 메서드

	//operators(연산자 우선순위)에 따라 expression 파싱하여 계산하기
	static long calculate(String expression, int op_index, String[] operators)
	{
		long result = 0;

		//연산자 기준으로 토크나이즈 한 string 리스트 가져오기
		String[] list = getTokenizedList(expression, op_index, operators);

		for(int i = 0;i < list.length;i++)
		{
			long value = 0;

			//연산자가 포함되어있다면 다시 한 번 파싱 필요
			if(isOperatorInExpression(list[i]))
				value = calculate(list[i], op_index + 1, operators);
			//피연산자만 존재하는 경우
			else
				value = Integer.parseInt(list[i]);

			//연산 결과
			result = getResult(result, value, operators, op_index, i);
		}

		return result;
	}

 우선 operators[op_index]가 현재 파싱할 연산자를 나타낸다. 해당 연산자를 기준으로 수식(expression)을 파싱한 뒤 거기서 나온 string 배열들을 각각 다시 calculate 하게 된다.

 이 때 만약 list[i]에 연산자가 포함이 되어있지 않다면 단일 피연산자라는 뜻이기에 바로 Integer 값을 반환해준다.

연산자가 포함되어있으면 calculate로 다시 파싱하는 과정을 거치게 된다.

 그리고 result에 최종적으로 operators[op_index]의 연산자에 따라 (*,+,-) 계산을 한 값을 저장하게 된다.

 

 

 아래는 전체 코드이다.

import java.util.*;


class Solution {

	static String op_list[] = {"+","-","*"};
	static boolean visited[] = new boolean[3];

	static long max = Long.MIN_VALUE;

	public static long solution(String expression) {

		String[] operators = new String[3];

		for(int i = 0;i < 3;i++)
		{
			operators[0] = op_list[i];
			visited[i] = true;
			recursive(1, 1, expression, operators);
			visited[i] = false;
		}

		return max;
	}

	//모든 연산자 우선순위 경우의 수 만들기
	static void recursive(int depth, int op_index, String expression, String[] operators)
	{
		if(depth == 3)
		{
			long result = calculate(expression, 0, operators);

			max = Math.max(max, Math.abs(result));
		}
		else
		{
			for(int i = 0;i < op_list.length;i++)
			{
				if(!visited[i])
				{
					visited[i] = true;
					operators[op_index] = op_list[i];
					recursive(depth+1, op_index+1, expression, operators);
					visited[i] = false;
				}
			}
		}
	}

	//operators(연산자 우선순위)에 따라 expression 파싱하여 계산하기
	static long calculate(String expression, int op_index, String[] operators)
	{
		long result = 0;

		//연산자 기준으로 토크나이즈 한 string 리스트 가져오기
		String[] list = getTokenizedList(expression, op_index, operators);

		for(int i = 0;i < list.length;i++)
		{
			long value = 0;

			//연산자가 포함되어있다면 다시 한 번 파싱 필요
			if(isOperatorInExpression(list[i]))
				value = calculate(list[i], op_index + 1, operators);
			//피연산자만 존재하는 경우
			else
				value = Integer.parseInt(list[i]);

			//연산 결과
			result = getResult(result, value, operators, op_index, i);
		}

		return result;
	}

	//연산자 기준으로 토크나이즈 한 string list 얻기
	static String[] getTokenizedList(String expression, int op_index, String[] operators)
	{
		StringTokenizer strtok = new StringTokenizer(expression, operators[op_index]);

		String[] list = new String[strtok.countTokens()];

		int k = 0;

		while(strtok.hasMoreTokens())
			list[k++] = strtok.nextToken();

		return list;
	}

	//연산 결과 얻기
	static long getResult(long result, long value, String[] operators, int op_index, int i)
	{
		if(operators[op_index].equals("+"))
			result += value;
		else if(operators[op_index].equals("-"))
		{
			if(i==0)
				result += value;
			else
				result -= value;
		}
		else
		{
			if(i==0)
				result = 1;
			result *= value;
		}
		return result;
	}


	//expression 안에 아무 연산자가 존재하는지 판단
	static boolean isOperatorInExpression(String expression)
	{
		if( expression.contains("+") || expression.contains("-") || expression.contains("*"))
			return true;
		return false;
	}
}