[프로그래머스] Lv.2 수식 최대화 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

 

문제 설명

+, -, * 3가지의 연산자만 들어있는 연산 수식이 주어집니다.

연산 수식은 "100-200*300-500+20"과 같이 숫자와 연산자가 포함된 String형태로 주어집니다.

+, -, *의 우선순위를 같은 순위 없이 바꿔 절댓값이 가장 큰 숫자를 구하는 것입니다.

예를 들어, 위의 연산에서 + > - > * 로 우선순위를 정한다면 수식의 결괏값은 22000입니다.

반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60420으로, 절댓값은 60420으로 가장 큽니다.

 

주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 만들 수 있는 절댓값이 가장 큰 수를 만들어 return 하도록 하는 solution 함수를 완성해 주세요.

---

💡 아이디어

일단 연산자가 3개밖에 주어지지 않고, expression의 길이가 3 이상 100 이하인 문자열로 주어지기 때문에

시간초과 가능성은 없을 것 같아 브루스포스, 즉 모든 것을 계산해 가장 큰 값을 찾는 방법을 사용했습니다.

 

📗 풀이과정

1. 우선순위를 저장할 HashMap을 만들고, +, -, * 의 우선순위를 바꿔 총 6가지의 조합을 모두 만들어 HashMap에 저장합니다.

static Map<Integer,Character> prior = new HashMap<>(); //우선순위_연산자

//연산자 우선순위 조합
//우선순위는 0, 1, 2 순으로 넣고, 0이 가장 우선되는 순위입니다.
for(int i=0;i<3;i++){
	for(int j=0;j<3;j++){
    	if(i==j) continue; //연산자 우선순위가 같으면 안됨
        for(int k=0;k<3;k++){
        	if(k==i || k==j) continue; //연산자 우선순위 같으면 안됨.
            
            prior.put(i,'+');// +의 우선순위는 i
            prior.put(j,'-');// -의 우선순위는 j
            prior.put(k,'*');// *의 우선순위는 k
        }
    }
}

 

2. +, -, * 의 연산자 우선순위를 설정했으면, expression을 우선순위에 맞게 계산하는 함수를 만듭니다.

(아래부터는 예시로 설명하겠습니다.)

2-1. 일단 들어온 expression의 숫자와 연산자를 분리해 각각 다른 ArrayList에 넣어줍니다.

2-2. 연산자 우선순위에 맞춰 연산을 수행하고, 연산에 사용된 num값들은 빼고 그 자리에 계산된 값을 집어넣습니다.

  또한 사용된 연산자는 빼줍니다.

 

 2-3. 2-2 연산을 더 이상 수행할 연산자가 없을 때까지 반복하고 나온 값을 반환해 줍니다.

 

3. 반환된 값의 절댓값이 answer값보다 크면 answer에 저장하고, 다음 우선순위 조합으로 넘어가 모든 우선순위 조합을 검사할 때까지 반복합니다.

 

---

전체 코드

import java.util.*;
class Solution {
    static Map<Integer,Character> prior = new HashMap<>();
    
    public long solution(String expression) {
        long answer = 0;
        
        //연산자 우선순위 조합
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(i==j) continue;
                for(int k=0;k<3;k++){
                    if(k==i || k==j) continue;
                    
                    prior.put(i,'+');
                    prior.put(j,'-');
                    prior.put(k,'*');
                    
                    long temp=Math.abs(culEx(expression));
                    //System.out.println(i+""+j+""+k+" "+temp);
                    if(temp>answer){
                        answer=temp;
                    }
                }
            }
        }
        
        return answer;
    }
    long culEx(String ex){
        
        ArrayList<Long> num = new ArrayList<>();//숫자
        ArrayList<Character> op = new ArrayList<>();//연산자
        
        int idx=0;
        for(int i=0;i<ex.length();i++){
            if(ex.charAt(i)=='+' || ex.charAt(i)=='-' || ex.charAt(i)=='*'){
                op.add(ex.charAt(i));
                num.add(Long.parseLong(ex.substring(idx,i)));
                idx=i+1;
            }
        }
        num.add(Long.parseLong(ex.substring(idx,ex.length())));
        //System.out.println(num+" "+op);
        
        while(op.size()>0){//더이상 계산할 연산자가 없을 때까지
            for(int p=0;p<3;p++){//연산자 우선순위
                for(int i=0;i<op.size();i++){//연산자 ArrayList에서 하나씩 읽어옴.
                    if(op.get(i)==prior.get(p)){//p우선순위의 연산자를 찾으면
                    
                        long cul=0l;
                        if(op.get(i)=='+') cul=num.get(i)+num.get(i+1);
                        else if(op.get(i)=='-') cul=num.get(i)-num.get(i+1);
                        else cul=num.get(i)*num.get(i+1);

                        num.remove(i);num.remove(i);//연산을 수행한 num값 없앰
                        num.add(i,cul);//그자리에 계산된 값 넣기
                        op.remove(i);//수행한 연산자 없애기
                        i--;//연산자를 하나 빼주기 때문에 
                             //ArrayList에서 다음 연산자를 읽을 때 차질이 생기지 않게 함.
                    }
                }
            }
        }
    
        return num.get(0);
    }
}