[백준] 14888번 : 연산자 끼워넣기 - JAVA [자바]

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

---

• 문제

 

 

 

 

 

백준에서 제공한느 삼성 SW 역량 테스트 기출 문제 중 하나다. (참고로 덧붙이자면 삼성 SW 역량 테스트의 경우 dp와 탐색 정도의 기본적인 알고리즘 풀이 능력은 갖추는 것을 추천한다. 자료구조는 뭐.. 당연 기초 중의 기초다.)

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이번 문제 또한 그동안 백트래킹을 통해 문제를 풀어보고 정확하게 이해했다면 정말 쉽게 접근 할 수 있다.

 

우리는 그동안 어떤 수가 주어지면 1부터 해당 수 까지 반복하며 재귀 호출을 통해 탐색하는 방법을 사용했다. 이 방법을 간단한 아이디어를 통해 바꾸면 된다.

 

어떻게 바꾸면 될까?

 

일단 주어지는 입력을 보면 다음과 같다.

첫째 줄 : 수의 개수

둘째 줄 : 수

셋째 줄 : 덧셈, 뺄셈, 곱셈, 나눗셈 각각의 개수

 

여기서 셋 째 줄을 입력 받고, 각 연산자를 배열로 두어 수를 두면 되지 않을까?

즉, 4칸의 배열에 각각 연산자의 개수를 입력하고, 반복문안에서 재귀호출을 해주는 것이다. 그리고 재귀호출 때 마다 해당 연산자 인덱스를 1 감소시키며 0이 된다면 다음 인덱스(연산자)로 넘어간다.

간단하게 코드로 보면 다음과 같다.

int[] number;	// 숫자
int[] operator;	// 연산자 개수
 
public static void dfs(int num, int idx) {
 
	for (int i = 0; i < 4; i++) {
		// 연산자 개수가 1개 이상인 경우
		if (operator[i] > 0) {
        
			// 해당 연산자를 1 감소시킨다.
			operator[i]--;
				
			switch (i) {
			
			case 0 : dfs(num + number[idx], idx + 1); break;
			case 1 : dfs(num - number[idx], idx + 1); break; 
			case 2 : dfs(num * number[idx], idx + 1); break;
			case 3 : dfs(num / number[idx], idx + 1); break;
				
			}
			// 재귀호출이 종료되면 다시 해당 연산자 개수를 복구한다.
			operator[i]++;
		}
	}
}

 

 

위와 같은 형식으로 재귀호출을 하면 모든 경우의 수를 구할 수 있다.

그리고 저 재귀호출과정에서 만약 모든 연산자를 썼을 경우(idx == N) 해당 값이 최대인지, 최소인지를 판별하면 된다.

 

그러면 전체 코드를 보며 좀 더 상세하게 보도록 하자.

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

알고리즘은 위에서 설명한 것을 보충하여 쓸 것이다. 전체적인 알고리즘 흐름은 같되, 입력의 방법만 바꾸어 성능 차이를 비교해보고자 한다. 어차피 출력방법을 바꾸어봤자 크게 출력할 것이 최댓값과 최솟값, 2개 뿐이므로 별 의미가 없다.

 

1 . Scanner 

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;
 
public class Main {
 
	public static int MAX = Integer.MIN_VALUE;	// 최댓값 
	public static int MIN = Integer.MAX_VALUE;	// 최솟값 
	public static int[] operator = new int[4];	// 연산자 개수 
	public static int[] number;					// 숫자 
	public static int N;						// 숫자 개수 
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		N = in.nextInt();
		number = new int[N];
 
		// 숫자 입력
		for (int i = 0; i < N; i++) {
			number[i] = in.nextInt();
		}
 
		// 연산자 입력
		for (int i = 0; i < 4; i++) {
			operator[i] = in.nextInt();
		}
 
		dfs(number[0], 1);
 
		System.out.println(MAX);
		System.out.println(MIN);
 
	}
 
	public static void dfs(int num, int idx) {
		if (idx == N) {
			MAX = Math.max(MAX, num);
			MIN = Math.min(MIN, num);
			return;
		}
 
		for (int i = 0; i < 4; i++) {
			// 연산자 개수가 1개 이상인 경우
			if (operator[i] > 0) {
 
				// 해당 연산자를 1 감소시킨다.
				operator[i]--;
 
				switch (i) {
 
				case 0:	dfs(num + number[idx], idx + 1);	break;
				case 1:	dfs(num - number[idx], idx + 1);	break;
				case 2:	dfs(num * number[idx], idx + 1);	break;
				case 3:	dfs(num / number[idx], idx + 1);	break;
 
				}
				// 재귀호출이 종료되면 다시 해당 연산자 개수를 복구한다.
				operator[i]++;
			}
		}
	}
 
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

앞서 알고리즘 설명에서 조건문은 작성하지 않았는데, 조건문은 간단하게 idx(인덱스이자 깊이를 의미)가 N이랑 같아지면 모든 연산자를 사용했다는 의미이므로, 해당 값이 최댓값인지, 최솟값인지를 보고 해당 값을 교체해주면 된다.

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static int MAX = Integer.MIN_VALUE;	// 최댓값 
	public static int MIN = Integer.MAX_VALUE;	// 최솟값 
	public static int[] operator = new int[4];	// 연산자 개수 
	public static int[] number;					// 숫자 
	public static int N;						// 숫자 개수 
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		N = Integer.parseInt(br.readLine());
		number = new int[N];
 
		// 숫자 입력 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			number[i] = Integer.parseInt(st.nextToken());
		}
 
		// 연산자 입력 
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < 4; i++) {
			operator[i] = Integer.parseInt(st.nextToken());
		}
 
		dfs(number[0], 1);
 
		System.out.println(MAX);
		System.out.println(MIN);
 
	}
 
	public static void dfs(int num, int idx) {
		if (idx == N) {
			MAX = Math.max(MAX, num);
			MIN = Math.min(MIN, num);
			return;
		}
 
		for (int i = 0; i < 4; i++) {
			// 연산자 개수가 1개 이상인 경우
			if (operator[i] > 0) {
 
				// 해당 연산자를 1 감소시킨다.
				operator[i]--;
 
				switch (i) {
 
				case 0:	dfs(num + number[idx], idx + 1);	break;
				case 1:	dfs(num - number[idx], idx + 1);	break;
				case 2:	dfs(num * number[idx], idx + 1);	break;
				case 3:	dfs(num / number[idx], idx + 1);	break;
 
				}
				// 재귀호출이 종료되면 다시 해당 연산자 개수를 복구한다.
				operator[i]++;
			}
		}
	}
 
}

 

 

 

크게 어렵지 않은 문제였을 것이다. 그냥 각 연산자의 개수만큼 완전탐색을 하여 모든 경우의 수를 탐색하면 된다!

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 20935327  -  방법 2 : BufferedReader 

채점 번호 : 20935316  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

문제가 쉬웠는지 정답률이 50%가 넘는다. 아마 대개 잘 풀으셨으리라 본다. 혹여 모르는 부분이나 설명을 추가로 해주었으면 하는 부분이 있다면 댓글 남겨주시면 빠르게 피드백 드리도록 하겠다.