Programmers - 수식 최대화(Java)

https://programmers.co.kr/learn/courses/30/lessons/67257?language=java 

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

 

풀이

입력으로 주어진 문자열을 숫자, 연산자로 분리

연산자의 우선순위에 대해 모든 경우의 수를 탐색

    - 경우의 수마다 계산하여 최대값과 비교 갱신

 

---

연산자, 숫자 분리

전역변수 정의

// 문자열의 숫자 부분
static List<Long> numList = new ArrayList<>();
// 문자열의 연산자 부분
static List<Character> optList = new ArrayList<>();
// set -> 문자열의 종류
static List<Character> optKind = new ArrayList<>();

입력 문자열의 탐색하여 연산자가 나올때까지 숫자를 StringBuilder에 append

연산자가 나온다면 StringBuilder을 long으로 형변환하여 숫자 List에 add

                         연산자 종류 Set과 연산자 List에 add

private static void splitExp(String exp) {
	char[] arr = exp.toCharArray();
	Set<Character> optSet = new HashSet<>();
	StringBuilder numberStr = new StringBuilder();
    
	for (char c : arr) {
		if (c == '+' || c == '-' || c == '*') {
			optSet.add(c);
			optList.add(c);
			numList.add(Long.valueOf(numberStr.toString()));
			numberStr = new StringBuilder();
		} else {
			numberStr.append(c);
		}
	}
    
	numList.add(Long.valueOf(numberStr.toString()));
	optKind = new ArrayList<>(optSet);
}

 

모든 경우의 우선순위 탐색

브루트 포스 알고리즘을 이용해 모든 경우의 수를 탐색

우선순위가 만들어졌다면 calc()함수로 이동/계산

계산된 값과 MAX를 비교 갱신하여 최대값을 업데이트

private static void priorityOrder(List<Character> order) {
	if (order.size() == optKind.size()) {
		Long now = calc(order);
		if(now>MAX)MAX=now;
		return;
	}
    
	for (int i = 0; i < optKind.size(); i++) {
		if (visit[i]) continue;
		visit[i] = true;
		order.add(optKind.get(i));
        
		priorityOrder(order);
        
		visit[i] = false;
		order.remove(order.size() - 1);
	}
}

 

 

우선순위에 대해 계산

우선순위에 맞춰서 탐색 계산

현재 우선순위의 연산자와 연산자 List가 같다면 nums[i]=calcOpt()로 계산

현재 위치의 연산자, 다음위치의 숫자 제거, 현재위치의 숫자에 계산 값을 기입

모든 연산자에 대해 탐색하게 되면 숫자 List에는 한개의 값만 남게됨(결과값)

private static Long calc(List<Character> order) {
	List<Long> copyNumList = new ArrayList<>(numList);
	List<Character> copyOptList = new ArrayList<>(optList);

	for (char opt : order) {
		for (int i = 0; i < copyOptList.size(); i++) {
			if (opt == copyOptList.get(i)) {
				copyNumList.set(i, calcOpt(copyNumList.get(i), copyNumList.get(i + 1), opt));
				copyNumList.remove(i + 1);
				copyOptList.remove(i);
				i--;
			}
		}
	}
	return Math.abs(copyNumList.get(0));
 }
 
 private static Long calcOpt(long a, long b, char opt) {
	long res = 0;
    
	if (opt == '+') {
		res = a + b;
	} else if (opt == '-') {
		res = a - b;
	} else {
		res = a * b;
	}
	return res;
}

---

전체 코드

import java.util.*;

class Solution {
    static long MAX = 0;
    static List<Long> numList = new ArrayList<>();
    static List<Character> optList = new ArrayList<>();
    static List<Character> optKind = new ArrayList<>();
    static boolean[] visit;

    public static long solution(String expression) {
        splitExp(expression);

        visit = new boolean[optKind.size()];
        List<Character> order = new ArrayList<>();
        priorityOrder(order);
        
        return MAX;
    }
    
    // 주어진 입력 문자열에서 숫자와 연산자를 분리
    private static void splitExp(String exp) {
        char[] arr = exp.toCharArray();
        Set<Character> optSet = new HashSet<>();
        StringBuilder numberStr = new StringBuilder();
        
        for (char c : arr) {
            if (c == '+' || c == '-' || c == '*') {
                optSet.add(c);
                optList.add(c);
                numList.add(Long.valueOf(numberStr.toString()));
                numberStr = new StringBuilder();
            } else {
                numberStr.append(c);
            }
        }
        numList.add(Long.valueOf(numberStr.toString()));
        optKind = new ArrayList<>(optSet);
    }    
    
    // 연산자의 우선순위 구하기
    private static void priorityOrder(List<Character> order) {
        if (order.size() == optKind.size()) {
            // 정해진 우선순위에 맞게 계산
            Long now = calc(order);
            // 계산된 값과 최대값을 비교/갱신
            if(now>MAX)MAX=now;
            return;
        }
        
        for (int i = 0; i < optKind.size(); i++) {
            if (visit[i]) continue;
            visit[i] = true;
            order.add(optKind.get(i));
            priorityOrder(order);
            visit[i] = false;
            order.remove(order.size() - 1);
        }
    }

    private static Long calcOpt(long a, long b, char opt) {
        long res = 0;
        if (opt == '+') {
            res = a + b;
        } else if (opt == '-') {
            res = a - b;
        } else {
            res = a * b;
        }
        return res;
    }
    
    // 연산자의 우선순위에 맞춰 계산
    private static Long calc(List<Character> order) {
        List<Long> copyNumList = new ArrayList<>(numList);
        List<Character> copyOptList = new ArrayList<>(optList);

        for (char opt : order) {
            for (int i = 0; i < copyOptList.size(); i++) {
                if (opt == copyOptList.get(i)) {
                    copyNumList.set(i, calcOpt(copyNumList.get(i), copyNumList.get(i + 1), opt));
                    copyNumList.remove(i + 1);
                    copyOptList.remove(i);
                    i--;
                }
            }
        }
        return Math.abs(copyNumList.get(0));
    }
}