[Java] 프로그래머스 - 수식 최대화 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

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

 

 

 

 

 

import java.util.*;

class Solution {
    boolean[] check; //방문 여부 체크용
    char[] list; //* + -가 들어있는 리스트
    long answer; //리턴용
    public long solution(String expression) {
        answer = 0;
        
       	//숫자들 모아놓을 배열
        ArrayList<Long> numbers = new ArrayList<>();
        //숫자 구분용
        String[] nTemp = expression.split("\\*|\\-|\\+");
        
        //숫자로 변환
        for (int i = 0; i < nTemp.length; i++) {
            numbers.add(Long.parseLong(nTemp[i]));
        }
        
        //연산기호 구분용
        char[] sTemp = expression.toCharArray();
       	
        //연산기호 담길 배열
        ArrayList<Character> sign = new ArrayList<>(); 
        
        //* + -면 추가
        for (int i = 0; i < sTemp.length; i++) {
            if (sTemp[i] == '*' || sTemp[i] == '+' || sTemp[i] == '-') {
                sign.add(sTemp[i]);
            }
        }
        
        check = new boolean[3];
        list = new char[]{'*', '+', '-'};
        
        //함수 호출
        func(numbers, sign);
        
        return answer;
    }
    
    public void func(ArrayList<Long> numbers, ArrayList<Character> sign) {
    	//다 계산 끝나면 숫자 하나만 남기 때문에 조건문이 이럼
        if (numbers.size() == 1 && sign.size() == 0) {
            //절대값으로 변환한 숫자와 answer와 비교해서 큰 쪽 담기
            answer = Math.max(answer, Math.abs(numbers.get(0)));
            return;
        } 
        
        //* + -을 for문으로 방문함
        for (int i = 0; i < list.length; i++) {
            if (check[i]) continue;
            
            check[i] = true;
            
            ArrayList<Long> numClone = (ArrayList<Long>) numbers.clone();
            ArrayList<Character> signClone = (ArrayList<Character>) sign.clone();
            
            while(signClone.indexOf(list[i]) != -1) {
                int p = signClone.indexOf(list[i]);
                
                long a = numClone.remove(p);
                long b = numClone.remove(p);
                signClone.remove(p);
                
                long c = (i == 0) ? a * b : (i == 1) ? a + b : a - b;
                numClone.add(p, c);
            }
            
            func(numClone, signClone);
            check[i] = false;
        }
    }
}

 

테스트 1 〉	통과 (0.38ms, 75.3MB)
테스트 2 〉	통과 (0.39ms, 72.9MB)
테스트 3 〉	통과 (0.42ms, 76.3MB)
테스트 4 〉	통과 (0.72ms, 75.1MB)
테스트 5 〉	통과 (0.56ms, 68.5MB)
테스트 6 〉	통과 (0.83ms, 75.3MB)
테스트 7 〉	통과 (0.83ms, 71.6MB)
테스트 8 〉	통과 (0.75ms, 74MB)
테스트 9 〉	통과 (0.92ms, 71.4MB)
테스트 10 〉	통과 (0.89ms, 73.1MB)
테스트 11 〉	통과 (0.73ms, 75.4MB)
테스트 12 〉	통과 (0.87ms, 73.6MB)
테스트 13 〉	통과 (1.22ms, 74.3MB)
테스트 14 〉	통과 (1.33ms, 91.1MB)
테스트 15 〉	통과 (2.72ms, 72.3MB)
테스트 16 〉	통과 (0.51ms, 69.9MB)
테스트 17 〉	통과 (0.72ms, 77.8MB)
테스트 18 〉	통과 (0.51ms, 74.5MB)
테스트 19 〉	통과 (0.57ms, 74.4MB)
테스트 20 〉	통과 (0.59ms, 87.8MB)
테스트 21 〉	통과 (1.02ms, 72.8MB)
테스트 22 〉	통과 (1.50ms, 76MB)
테스트 23 〉	통과 (0.42ms, 75.1MB)
테스트 24 〉	통과 (1.14ms, 69.6MB)
테스트 25 〉	통과 (1.00ms, 73MB)
테스트 26 〉	통과 (0.40ms, 72.7MB)
테스트 27 〉	통과 (1.44ms, 74.2MB)
테스트 28 〉	통과 (1.34ms, 73.3MB)
테스트 29 〉	통과 (0.98ms, 71.8MB)
테스트 30 〉	통과 (1.40ms, 76.4MB)

 

 

 

 

 

중요한 포인트는 split( )을 이용해서 *, +, - 를 구분해서 숫자만 골라낼 때 그냥 "*|+|-"가 아닌 "\\*|\\+|\\-"로 입력을 해야 함