[JAVA] 프로그래머스 - 수식최대화

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

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

문제에서 나타난 연산자의 수가 3개이기 때문에 경우의 수는 3!=6가지이다.

깊이 우선 탐색(dfs)은 어딜가나 나오기 때문에 항상 복습하는 습관을 길러야겠다!!!!!고 생각한 문제.

코드를 분석하면 다음과 같다.

1. 전역변수

	public static char[] prior = {'+','-','*'};
	public static ArrayList<Character> op = new ArrayList<Character>();
	public static ArrayList<Long> num = new ArrayList<Long>();
	public static boolean[] checked = new boolean[3];
	public static long answer = 0;

- char 배열에 연산자를 미리 담아놓음 -> 나중에 우선순위를 매길 때, prior에서 가져와 인덱스 0부터 넣기 위함

- op와 num은 String으로 받은 expression을 숫자와 연산자를 구별하여 각각 담은 ArrayList에 담음

- checked는 깊이우선탐색시 우선순위의 모든 경우의 수를 구하기 위해 미리 false로 초기화 시켜놓음

 

2. 메인 함수(Solution)

public static void main(String[] args){
		String expression = "100-200*300-500+20";
		StringBuilder nb = new StringBuilder();
		
		for(int i=0; i<expression.length(); i++) {
			char ch = expression.charAt(i);
			if(ch<'0' || ch>'9') {
				op.add(ch);
				num.add(Long.parseLong(nb.toString()));
				nb.setLength(0);
			}				
			else
				nb.append(ch);
		}
		num.add(Long.parseLong(nb.toString()));
		
		dfs(0, new char[3]);
		System.out.println(answer);
	}

- String으로 받은 expression에서 charAt을 사용하여 숫자에 해당하면 Stringbuilder에 추가하고, 연산자면 op에 추가

- op와 num에 모두 추가 끝났으면 모든 우선순위 경우에 따른 결과값을 검사하여 절대값이 가장 큰 값을 answer에 저장

 

3. 계산하기(calc)

	//계산 메소드
	public static long calc(long num1, long num2, char ch) {
		switch(ch) {
		case '+':return num1+num2;
		case '-':return num1-num2;
		default :return num1*num2;
		}
	}

 

 

3. 깊이우선탐색(dfs) ★중요★

//순서에 맞게 연산
	public static void dfs(int cnt, char[] ops) {
		//3개의 연산자 모두 실행되었을 때
		if(cnt==3) {
			//num과 op의 내용을 복사해옴
			ArrayList<Long> cNums = new ArrayList<Long>(num);
			ArrayList<Character> cOps = new ArrayList<Character>(op);
			
			for(int i=0; i<ops.length; i++) {
				for(int j=0; j<cOps.size(); j++) {
					if(cOps.get(j)==ops[i]) {
						Long res = calc(cNums.remove(j),cNums.remove(j),ops[i]);
						cNums.add(j,res);
						cOps.remove(j);
						j--;	//삭제했기 때문에 j번째 연산자 다시 확인
					}
				}
			}
			answer = Math.max(answer, Math.abs(cNums.get(0)));
			return ;
		}
		
		//우선순위 모든 경우의 수 - 초기화된 char 배열에 넣음 ***
		for(int i=0; i<3; i++) {
			if(!checked[i]) {
				checked[i]=true;
				ops[cnt] = prior[i];
				dfs(cnt+1, ops);
				checked[i]=false;
			}
		}
	}

- 우선 우선순위를 결정하기 위해 3번 탐색을 해줘야 한다 -> cnt가 3이 될때까지 재귀 호출함

- false로 초기화된 checked를 이용하여 하나씩 true를 걸어주고 prior에 있는 연산자를 ops에 차례로 넣어줌

(이 로직이 가장 중요한듯 하다.. 사실상 이 문제에서 가장 생각하기 어려운 부분)

- 깊이우선 탐색에 의해 모든 checked가 true로 변하면, ops도 연산자로 다 채워지고, cnt는 3이 된다.

- cnt가 3이 되면, ArrayList 두 개를 생성하여 각각 num과 op를 복사해 넣어놓는다

- 그리고 우선순위가 담긴 연산자들(ops)의 순서에 따라 각각 연산을 진행한다.

- 해당 우선순위의 연산자(i번째 ops)와 같은 연산자(j번째 cOps)이 나왔을 때 연산을 진행 후 j번째에 집어넣음

(해당 연산자와 숫자는 list에서 삭제 시킨 후 결과값을 j번째에 넣어줌)

※ ArrayList는 remove를 진행하면서 해당 인덱스의 값을 반환하고 모든 인덱스가 한개씩 앞으로 당겨짐) 

 

4. 전체코드

import java.util.*;


public class Solution{
	public static char[] prior = {'+','-','*'};
	public static ArrayList<Character> op = new ArrayList<Character>();
	public static ArrayList<Long> num = new ArrayList<Long>();
	public static boolean[] checked = new boolean[3];
	public static long answer = 0;
	
	public static void main(String[] args){
		String expression = "100-200*300-500+20";
		StringBuilder nb = new StringBuilder();
		
		for(int i=0; i<expression.length(); i++) {
			char ch = expression.charAt(i);
			if(ch<'0' || ch>'9') {
				op.add(ch);
				num.add(Long.parseLong(nb.toString()));
				nb.setLength(0);
			}				
			else
				nb.append(ch);
		}
		num.add(Long.parseLong(nb.toString()));
		
		dfs(0, new char[3]);
		System.out.println(answer);
	}
	
	//계산 메소드
	public static long calc(long num1, long num2, char ch) {
		switch(ch) {
		case '+':return num1+num2;
		case '-':return num1-num2;
		default :return num1*num2;
		}
	}
	
	//순서에 맞게 연산
	public static void dfs(int cnt, char[] ops) {
		//3개의 연산자 모두 실행되었을 때
		if(cnt==3) {
			//num과 op의 내용을 복사해옴
			ArrayList<Long> cNums = new ArrayList<Long>(num);
			ArrayList<Character> cOps = new ArrayList<Character>(op);
			
			for(int i=0; i<ops.length; i++) {
				for(int j=0; j<cOps.size(); j++) {
					if(cOps.get(j)==ops[i]) {
						Long res = calc(cNums.remove(j),cNums.remove(j),ops[i]);
						cNums.add(j,res);
						cOps.remove(j);
						j--;	//삭제했기 때문에 j번째 연산자 다시 확인
					}
				}
			}
			answer = Math.max(answer, Math.abs(cNums.get(0)));
			return ;
		}
		
		//우선순위 모든 경우의 수 - 초기화된 char 배열에 넣음 ***
		for(int i=0; i<3; i++) {
			if(!checked[i]) {
				checked[i]=true;
				ops[cnt] = prior[i];
				dfs(cnt+1, ops);
				checked[i]=false;
			}
		}
	}
}

 

공부는 열심히,, 꾸준히 해야겠다

[참조]

https://geunzrial.tistory.com/10