본문 바로가기
알고리즘 문제/프로그래머스

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

by 건복치 2021. 1. 29.
반응형

문제

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

 

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

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

programmers.co.kr

설명

연산을 위해 주어진 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

Programmers Algoritm. Contribute to KwonMinha/Programmers development by creating an account on GitHub.

github.com

 

반응형

댓글