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

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

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

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Solution {
	    public long solution(String expression) {
	    	char priority[][]= {
	    			{'*','+','-'},
	    			{'*','-','+'},
	    			{'+','*','-'},
	    			{'+','-','*'},
	    			{'-','*','+'},
	    			{'-','+','*'},
	    	};
	    	
	        String num="";
	        List<Long> nums=new ArrayList<>();
	        List<Character> ops=new ArrayList<>();
	        
	        for(int i=0; i<expression.length(); i++) {
	        	char ch=expression.charAt(i);
	        	if(Character.isDigit(ch)) num+=ch; //숫자라면 
	        	else { //숫자 아니라면
	        		ops.add(ch);
	        		nums.add(Long.parseLong(num));
	        		num="";
	        	}
	        }
	        nums.add(Long.parseLong(num));
	        return solve(nums,ops,priority);
	    }

		private long solve(List<Long> nums, List<Character> ops, char[][] priority) {
			char opCheck='+';
			long answer=0;
			
			for(int k=0; k<6; k++) {
				Stack<Long> num=new Stack<>();
				Stack<Character> op=new Stack<>();
				for(int i=0; i<nums.size(); i++) {
					num.add(nums.get(i));
					if(i!=nums.size()-1) {
						opCheck=ops.get(i);
						//우선순위가 나보다 같거나 높은 우선순위  위로는 못들어감 !!!!
						while(true) {
							if(op.isEmpty() || priorityCheck(op.peek(), opCheck,k,priority)) { //연산자 잘 들어간다면 !
								op.add(opCheck);
								break;
							}
							else { //빼서 계산 ㄱ
								long b=num.pop();
								long a=num.pop();
								num.push(cal(a,b,op.pop()));
							}
						}
					}
				}
				
				//남은 연산자수만큼 계산 
				int size=op.size();
				for(int i=0; i<size; i++) {
					long b=num.pop();
					long a=num.pop();
					num.push(cal(a,b,op.pop()));
				}
				answer = Math.max(Math.abs(num.pop()), answer);
			}
			return answer;
		}

		private long cal(long a, long b, char pop) {
			switch(pop) {
			case '+': return a+b;
			case '-': return a-b;
			case '*': return a*b;
			}
			return 0;
		}

		private boolean priorityCheck(char peek, char opCheck,int k, char[][] priority) {
			int peekPriority=0;
			int opCheckPriority=0;
			
			for(int i=0; i<3; i++) {
				if(priority[k][i]==peek) peekPriority=i; //현재 스택에 들어가있는 값
				if(priority[k][i]==opCheck) opCheckPriority=i; //들어갈 값 
			}
			if(peekPriority > opCheckPriority) return true;
			return false;
		}
	}

 

소요시간 : 1시간

 

Level 2 치고는... 처리할게 많아서 시간이 오래 걸렸습니다..ㅜㅜ

List안에 Long으로 처리를 해야 하는데 Integer로 해서 이거 찾는데 좀 오래 걸렸습니다!!

 

우선 로직을 보면

 

숫자와 연산자를 따로 담아줍니다!

priority배열에다가 6가지의 우선순위를 미리 넣어줍니다.

 

그리고 이 6가지 연산자를 기준으로 for문을 돌려줍니다.

그 안에서 스택 2개를 이용해서 계산을 해줍니다!

 

계산하는 방법은 이렇습니다.

 

1. 숫자가 들어오면 무조건 Stack(num)에 푸시한다

2. 연산자가 들어오면 현재 Stack(op)의 가장 위의 연산자와 우선순위를 비교한다

   2-1. 만약 Stack의 가장 위의 연산자보다 우선순위가 높다면 Stack에 Push하고 다음으로 넘어간다.

   2-2. 만약 Stack의 가장위의 연산자와 우선순위가 같거나 높다면 Stack(op)에서 연산자를 빼고 Stack(num)에서 숫자             2개를 빼서 계산하고 다시 Stack(num)에 Push 해준다.

 

이렇게 하면 답이 나옵니다!!

이렇게 풀기 위해서는 스택을 통해 계산하는 방법(연산자 우선순위에 따른 스택 변경)을 알아야 합니다!!!