[JAVA]BOJ(백준) - 연산자 끼워넣기 - 14888

- 문제 내용

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

- 문제 접근 방법

처음 생각했던 방법은 수열이 주어졌을때 어차피 수의 순서는 바꾸지 못하기때문에 순서대로만 찍어내서 계산하고 계산한 값을 담을 변수하나를 추가해주는 것이다. 그리고 값의 계산은 연산자만 바꿔가면서 모든 경우의수를 알아보는 것이므로 재귀함수의 for Loop의 범위는 연산자 배열을 만들어서 그 크기만큼 돌리면 MAX, MIN 값이 구해진다고 생각했다.

정리하면

• 수열을 담을 배열 1개
• 연산자를 담을 배열 1개
• 수열을 계산한 값을 담을 변수 1개
• 재귀함수 종료조건은 수열의 수를 다썼을때 즉, N값과 비교할 수 있는 변수 1개

4개로 코드를 짜게됐다. 그리고 참고로 다른분의 코드가 더 좋아서 참조하게 됐는데 코드를 살펴보자ㅎㅎ

---

- 풀이

package org.boj.operator;

import java.util.Scanner;

public class BOJ_14888 {
	static int MAX = Integer.MIN_VALUE;
	static int MIN = Integer.MAX_VALUE;
	static int[] suArr; //수열 배열
	static int[] operator; //연산자 배열
	
	public void solution(int N, int depth, int temp) {
		if(depth == N) {
			MAX = Math.max(MAX, temp);
			MIN = Math.min(MIN, temp);
			return;
		}
		
		for(int i=0; i<4; i++) {
			if(operator[i]<=0) {continue;} //만약 i에 해당하는 요소가 0이면 해당 연산자를 다썼거나 처음부터 없는것이므로 다음 i로 넘어감.
			
			operator[i]--; //해당 요소가 있으면 사용되는 것이기에 1을 빼준다.
			
			switch (i) {//switch문을 통해 i가 "0-> + , 1-> - , 2-> * , 3-> /"로 경우를 나눠 재귀를 시작.
			case 0:	solution(N ,depth+1, temp+suArr[depth]); break;
			
			case 1:	solution(N ,depth+1, temp-suArr[depth]); break;
			
			case 2:	solution(N ,depth+1, temp*suArr[depth]); break;
			
			case 3:	solution(N ,depth+1, temp/suArr[depth]); break;
			}

			operator[i]++; //재귀가 다끝나면 다른 경우의수를 찾아봐야 하기때문에 다시 i요소에 1을 증가

		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int operatorCnt = 0;
		suArr = new int[N];
		operator = new int[4];
		
		for(int i=0; i<N; i++) { //N크기만큼 차례대로 수를 입력해 담는다
			suArr[i]=sc.nextInt();
		}
		
		for(int i=0; i<4; i++) { //연산자도 마찬가지로 담아준다.
			operator[i]=sc.nextInt();
		}
		sc.close();
		
		for(int x:operator) { //연산자의 총 개수를 카운트
			operatorCnt += x;
		}
	
		if(operatorCnt == N-1) { //연산자의 개수 = 수의 개수-1 일때만 실행
			new BOJ_14888().solution(N, 1 , suArr[0]);
		}
		
		System.out.println(MAX);
		System.out.println(MIN);
	}
}

내가 이해한대로 왠만한건 다 주석을 달았는데, 처음에 내가 짰던 코드는 temp 값을 list 에 전부 담아서 MAX, MIN을 찾았었고, switch문 대신 if문을 사용했었다. 보다시피 다른분이 짰던 switch가 훨씬 간결하고 보기 좋다.

그리고 MAX변수에 MIN_VALUE를 담아줌으로써 재귀의 종료조건이 될때마다 MAX 값을 갱신해줄수 있게 된다. list에 모든값을 담아서 최대,최소 값을 출력하는 것보다 훨씬 효율적이다... MAX_VALUE와 MIN_VALUE도 활용해줄수 있을때 활용해주자.

 

아 그리고 참고로 문제에서 나왔던 음수값을 나누는 경우는 언어마다 차이점이 있다곤 하는데 Java의 경우 그냥 음수자체를 나눠줘도 양수값으로 몫이 나오게 되는걸로 조언 받았고, 음수일때 따로 조건문을 안달아줘도 된다고 한다!! 개이득 ㅎㅎㅎ

---

- 마치며

요즘 백트래킹 공부를 하고 있는데 이건뭐 할때마다 어려운 기분이다.. 그래도 처음 접했을땐 감도 안잡혔는데 지금은 대충 이렇게하면 되지않을까 라는 생각을 할수 있게됐다ㅎㅎ 발전한 기분!