본문 바로가기
카테고리 없음

[카카오 인턴] 수식 최대화 - java

by minkang 2021. 4. 30.

 

programmers.co.kr/learn/courses/30/lessons/67257

 

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

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과

programmers.co.kr

class Solution {
	public long solution(String expression) {
		ArrayList<Long> numbers = new ArrayList<Long>();
		ArrayList<Character> operator = new ArrayList<Character>();

		StringTokenizer st = new StringTokenizer(expression, "+|-|*|/");
		while (st.hasMoreTokens()) {
			numbers.add(Long.parseLong(st.nextToken()));
		}
		for (int i = 0; i < expression.length(); i++) {
			if (expression.charAt(i) < '0' || expression.charAt(i) > '9') {
				operator.add(expression.charAt(i));
			}
		}

		char order[] = new char[4];
		boolean check[] = new boolean[4];
		max =0;
		permu(0, 0, order, numbers, operator, check);
		long answer = max;
		return answer;
	}

	// 0=+, 1=-, 2=*, 3=/
	static long max;
	private void permu(int idx, int cnt, char[] order, ArrayList<Long> numbers, ArrayList<Character> operator,
			boolean[] check) {
		if (cnt == 4) {
			ArrayList<Long> copyNumbers = new ArrayList<Long>();
			copyNumbers.addAll(numbers);
			ArrayList<Character> copyOperator = new ArrayList<Character>();
			copyOperator.addAll(operator);

			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < copyOperator.size(); j++) {
					if (order[i] == copyOperator.get(j)) {
						if(order[i] == '+') {
							copyNumbers.set(j, copyNumbers.get(j)+copyNumbers.get(j+1));
						}
						else if(order[i] =='-') {
							copyNumbers.set(j, copyNumbers.get(j)-copyNumbers.get(j+1));
						}
						else if(order[i] == '*') {
							copyNumbers.set(j, copyNumbers.get(j)*copyNumbers.get(j+1));
						}
						else {
							copyNumbers.set(j, copyNumbers.get(j)/copyNumbers.get(j+1));
						}
						copyNumbers.remove(j+1);
						copyOperator.remove(j);
						j--;
					}
				}
			}
			if( Math.abs(copyNumbers.get(0)) > max) {
				max = Math.abs(copyNumbers.get(0));
			}
		}

		for (int i = 0; i < 4; i++) {
			if (check[i] == false) {
				check[i] = true;
				if (i == 0) {
					order[cnt] = '+';
				} else if (i == 1) {
					order[cnt] = '-';
				} else if (i == 2) {
					order[cnt] = '*';
				} else if (i == 3) {
					order[cnt] = '/';
				}
				permu(i + 1, cnt + 1, order, numbers, operator, check);
				check[i] = false;
			}
		}
	}
}

우선 가변적으로 연산을 하기위해 ArrayList로 숫자와 연산자를 받았습니다.

그 다음 순열을 통해 연산자 우선순위를 정하였고 순위에 따라 계산했습니다.