[프로그래머스 - Java] 수식 최대화 (2020 카카오 인턴십)

문제

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

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

설명

연산을 위해 주어진 String 형태의 수식을 숫자와 연산자로 구분해 ArrayList에 저장한다.

(모두 한 번에 expList라고 저장해서 풀기도 했었는데, 5개 정도의 테스트 케이스에서 런타임 에러 난다..ㅠㅠ왜지..?)

 

숫자의 경우 long으로 저장하고 계산한다.

 

+, -, * 3개의 연산자를 바탕으로 순열을 구해 연산자 우선순위를 정한다.

 

구해진 순열을 바탕으로 계산을 한다.

연산자 리스트의 i번째 연산자는 숫자 리스트의 i번째와 i+1번째 숫자와 대응된다.

모든 계산이 끝났다면 숫자리스트의 0번째 인덱스에 하나의 결과 값만 남았을 것이다.

 

절댓값으로 answer에 있는 값과 비교해 더 큰 값을 answer값으로 갱신한다.

전체 코드

import java.util.*;

class Solution {
	public static long answer = Long.MIN_VALUE;
	
	public static ArrayList<Long> numList = new ArrayList<>(); // 숫자 담을 리스트 
	public static ArrayList<String> operList = new ArrayList<>(); // 연산자 담을 리스트 
	
	public static String[] oper = {"+", "-", "*"};
	public static String[] output = new String[3]; // 순열 결과 담을 배열 
	public static boolean[] visited = new boolean[3]; 
    
    public long solution(String expression) {
		String n = "";
		for(int i = 0; i < expression.length(); i++) {
			char exp = expression.charAt(i);
			if(exp == '+' || exp == '-' || exp == '*') {
				operList.add(exp + "");
				numList.add(Long.parseLong(n));
				n = "";
			} else {
				n += exp;
			}
		}  
		// 마지막 숫자 삽입 
		numList.add(Long.parseLong(n));
	
		//순열 만들기
		per(0, oper.length);
		
		return answer;
	}

	//순열 찾기
	static void per(int depth, int r) {
		if(depth == r) {
			solve(); // 연산 
		
			return;
		}

		for(int i = 0; i < oper.length; i++) {
			if(!visited[i]) {
				visited[i] = true;
				output[depth] = oper[i];
				per(depth + 1, r);  
				visited[i] = false;
			}
		}
	}
    
	// 연산 
	static void solve() {
		// 연산자 우선 순위에 따른 값을 얻기 위해 List 복사 
		ArrayList<String> oper = new ArrayList<String>();
		oper.addAll(operList);
		
		ArrayList<Long> num = new ArrayList<Long>();
		num.addAll(numList);
		
		for(int i = 0; i < output.length; i++) {
			String curOper = output[i]; // 현재 우선순위 연산자 
			
			for(int j = 0; j < oper.size(); j++) {
				
				if(oper.get(j).equals(curOper)) { // 현재 우선순위에 맞는 연산자일 경우 
					long n1 = num.get(j);
					long n2 = num.get(j+1);
					long res = cal(n1, n2, curOper);
					
				
					num.remove(j+1); // 숫자 삭제 
					num.remove(j);
					oper.remove(j); // 연산자 삭제 
					
	
					num.add(j, res); // 연산 결과 넣기 
			
					j--; // 삭제했으니 인덱스 하나 줄여주기 
				}
			}
		}
		
		answer = Math.max(answer, Math.abs(num.get(0)));
	}
	
	// 수식 계산 
	static long cal(long n1, long n2, String o) {
		long res = 0;
		switch(o) {
		case "+" :
			res = n1 + n2;
			break;
		case "-" :
			res = n1 -n2;
			break;
		case "*" :
			res = n1 * n2;
			break;
		}
		
		return res;
	}

}

GITHUB

github.com/KwonMinha/Programmers/blob/master/2020_Kakao_Internship/src/MaximizeFormula.java

KwonMinha/Programmers