[BaekJoon] 7490 0 만들기 (Java)

1.  문제 링크

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

2.  문제

요약

• 1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N에 '+'나 '-' 또는 ' '(공백)을 숫자 사이에 삽입합니다.
• +는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 의미합니다.
• 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지 살핍니다.
• N이 주어졌을 때, 수식의 결과가 0이 되는 모든 수식을 찾는 문제입니다.
• 입력: 첫 번째 줄에 10보다 작은 테스트 케이스의 개수가 주어지고 두 번째 줄부터 (테스트 케이스의 개수)개의 줄에는 3보다 크거나 같고 9보다 작거나 같은 자연수 N이 주어집니다.
• 출력: 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력합니다. 테스트 케이스의 결과는 한 줄을 띄워 구분합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static String[] operator = {"+", "-", " "};
	static ArrayList<String> expression;
	public boolean calculate(String exp) {
		StringTokenizer st = new StringTokenizer(exp, "+|-", true);
		int result = Integer.parseInt(st.nextToken());
		while(st.hasMoreTokens()) {
			String temp = st.nextToken();
			if(temp.equals("+")) {
				result += Integer.parseInt(st.nextToken());
			} else {
				result -= Integer.parseInt(st.nextToken());
			}
		}
		if(result == 0) {
			return true;
		}
		return false;
	}
	
	public void getAllCase(int num, String e) {
		if(num == n) {
			String exp = e.replaceAll(" ", "");
			if(calculate(exp)) {
				expression.add(e);
			}
			return;
		}
		for(int i = 0; i < 3; i++) {
			getAllCase(num + 1, e + operator[i] + Integer.toString(num + 1));
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Main m = new Main();
		int test_num = Integer.parseInt(br.readLine());
		for(int i = 0; i < test_num; i++) {
			n = Integer.parseInt(br.readLine());
			expression = new ArrayList<>();
			m.getAllCase(1, "1");
			Collections.sort(expression);
			for(String e : expression) {
				bw.write(e + "\n");
			}
			bw.write("\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}
}

4.  접근

• 수식을 만들기 위해 getAllCase() 함수를 이용합니다.
• 해당 함수는 정수형 num과 문자열 e를 파라미터로 갖는데, 정수형 num은 수열에서 현재 숫자를 말하고 문자열 e는 지금까지 만든 수식을 의미합니다.
• 1부터 오름차순으로 N까지 수열을 형성하기 때문에 초기에 num은 1, e 또한 "1"로 시작합니다.
• +, -, 공백 각각을 이용하여 재귀함수를 통해 수식을 완성해가고 수식이 완성됐으면 해당 수식이 0이 되는지 확인한 후에 백트래킹을 통해 이전으로 돌아가 다른 연산자 혹은 공백을 집어넣어 수식들을 만듭니다.
• 만약 호출된 재귀함수의 num이 N과 같다면 수열의 마지막까지 도달한 것이기 때문에 더이상 해당 수식에 대해서는 재귀함수 호출을 하지 않고 해당 수식이 0이 되는지 확인합니다.
• 공백은 두 숫자를 이어 붙이는 것을 의미하기 때문에 공백을 빈 문자열로 변경하여 두 숫자를 이어 붙여주고 해당 수식이 0이 되는지 확인합니다.
• 확인할 때는 + 또는 -를 기준으로 문자열을 나눠주고 이 때 StringTokenizer에서 returnDelims 속성을 true로 하여 +, - 또한 token에 포함시켜줍니다.
• 해당 수식의 답을 나타내는 result 변수를 수식의 첫 번째 숫자로 값을 초기화시키고 StringTokenizer가 다음 token을 갖고 있을 때까지 반복문을 돌며 +와 -일 때를 나누어 계산을 진행합니다.
  * 만약 StringTokenizer의 다음 token이 +라면 result에 +의 다음 token인 숫자를 더해줍니다.
  • 만약 StringTokenizer의 다음 token이 +가 아니라면 -라는 뜻이므로 result에 -의 다음 token인 숫자를 빼줍니다.
• 계산을 진행한 후에 result값이 0이라면 해당 수식을 수식의 결과가 0이 되는 모든 수식을 나타내는 ArrayList expression에 넣어주고 다른 수식들을 확인합니다.
• 모든 수식들을 확인한 후에 expression을 ASCII 순서에 따라 정렬해주고 각 수식들을 출력합니다.