[백준] 14888번 : 연산자 끼워넣기 (JAVA)

이번에는 백트래킹 문제 중 삼성 SW 역량 테스트 기출문제 1번인 "연산자 끼워넣기" 문제를 풀었다.

 

백트래킹에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/3

알고리즘 - 백트래킹(Backtracking)

 

바로 앞 문제인 2580번 : 스도쿠 에 대한 내용은 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/10

[백준] 2580번 : 스도쿠 (JAVA)

---

<문제>

<문제 해석>

백트래킹을 이용하여 숫자와 연산자의 갯수가 주어질 때 만들 수 있는 연산식 중 최댓값 최솟값을 구해라.

 

 

<문제 해결>

앞에서 계속 풀었던 백트래킹 문제들과 비슷한 유형이다.

숫자 사이에 연산자를 넣어 계산해주어 최댓값과 최솟값을 구하는 과정을 반복하면 될 것이라고 생각했다.

 

연산자를 앞에서부터 차례대로 사용하면서 사용할 때마다 -1 를 해주고,

연산자의 갯수가 0이 되면 다음 연산자를 사용하게 한다.

 

 

<알고리즘>

1. 입력받은 숫자를 ar 배열에 담는다.

2. 입력받은 연산자의 갯수를 operator 배열에 담는다.

3. 연산자의 갯수를 판별해 연산자의 갯수가 0보다 크면

4. 연산자의 종류를 판별해 연산식을 계산한다.

5. 1, 2, 3, 4 의 과정을 반복한다.

6. 계산한 값이 최댓값, 최솟값인지 판별한다.

 

 

연산자의 종류를 판별하는 식을

1. if-else 문

2. switch문

두 가지 모두 사용해보았다.

확실히 switch문이 더 가독성이 좋은 것 같다.

 

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;

public class Main {	
	static int n;
	static int[] ar;
	static int[] operator = new int[4];
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		ar = new int[n];
		for(int i=0;i<n;i++) {
			ar[i] = sc.nextInt();
		}
		for(int i=0;i<4;i++) {
			operator[i] = sc.nextInt();
		}
		
		back(ar[0],1);
		System.out.println(max);
		System.out.println(min);
	}
	
	static void back(int number, int index) {
		
		if(index == n) {
			max = Math.max(max, number);
			min = Math.min(min, number);
			return;
		}
		
		for(int i=0;i<4;i++) {
			if(operator[i] > 0) {
				operator[i]--;
				
                //1. if-else 사용
                //2. switch 사용
                
                //1. if-else 사용하는 방법
				if(i == 0) {
					back(number+ar[index],index+1);
				}else if(i == 1) {
					back(number-ar[index],index+1);
				}else if(i == 2) {
					back(number*ar[index],index+1);
				}else {
					back(number/ar[index],index+1);
				}
				
                //2. switch 사용하는 방법
//				switch(i) {
//				
//				case 0: back(number + ar[index], index+1); break;
//				case 1: back(number - ar[index], index+1); break;
//				case 2: back(number * ar[index], index+1); break;
//				case 3: back(number / ar[index], index+1); break;
//				}
				
				operator[i]++;
			}
		}
		
	}

}

 

 

---

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

14888번: 연산자 끼워넣기