[BOJ] 백준 7490번 0 만들기 (Java)

#7490 0 만들기

난이도 : 골드 5

유형 : 문자열 / 조합

7490번: 0 만들기

▸ 문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

▸ 입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

▸ 출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다

 

문제 풀이  

모든 조합을 구하여 수식이 0이 되는 조합을 구해주면 된다. 조합을 분기하면서 그때마다 값을 계산해주면서 풀어도 되기는 한데 나는 결과값을 온전히 받아 파싱하는 방법으로 구현했다. 물론 파싱하는 연산이 추가되기 때문에 성능은 더 좋지 않으나 그냥 절차대로 로직을 작성하여 풀이하고 싶었다.

 

3가지 조건으로 조합 나누기

재귀함수를 사용하여 '+', '-', ' ' 3가지 방향으로 1부터 n까지 모든 조합을 구한다. 이때마다 계산된 값을 구할 수 있는데 간단히 수식만 뽑아보면 다음과 같이 작성할 수 있다.

static void comb(int num, int len, String str){
    if(len == n) {
        if(calculate(str) == 0) {
            sb.append(str+"\n");
        }
        return;
    }

    comb(num+1, len+1, str+ ' ' + (num+1));
    comb(num+1, len+1, str+ '+' + (num+1));
    comb(num+1, len+1, str+ '-' + (num+1));

}

 

0이되는 수식 구하기

n까지 모든 조합을 뽑았으면 이젠 구해진 수식(str)을 계산하여 0이되는 수식을 구해주면 된다. 파싱하는 과정은 다음과 같다.

1. 공백 제거하기
2. 문자열을 Integer로 변환 후 Iterator 함수에 담기
3. 문자열을 순차탐색하여 '+', '-' 연산을 Iterator에 담긴 순서대로 계산하기

static int calculate(String str){
    str = str.replaceAll(" ", "");
    Iterator<Integer> it= Arrays.stream(str.split("[+,-]"))
            .map(Integer::parseInt)
            .collect(toList()).iterator();
    int result = it.next();
    for(int i=0; i<str.length(); i++) {
        if(str.charAt(i) == '+') {
            result += it.next();
        }else if(str.charAt(i) == '-') {
            result -= it.next();
        }
    }
    return result;

}

 

이렇게 구해진 모든 수식을 출력해주면 된다.

 

풀이 코드 

import java.io.*;
import java.util.*;
import static java.util.stream.Collectors.toList;

public class Main {

	static int n;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int t = Integer.parseInt(br.readLine());
		while(t-- > 0) {
			n = Integer.parseInt(br.readLine());
			comb(1,1,"1");
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	// +, -, ' '
	static void comb(int num, int len, String str){
		
		if(len == n) {
			if(calculate(str) == 0) {
				sb.append(str+"\n");
			}
			return;
		}
		
		comb(num+1, len+1, str+ ' ' + (num+1));
		comb(num+1, len+1, str+ '+' + (num+1));
		comb(num+1, len+1, str+ '-' + (num+1));
		
	}
	
	static int calculate(String str){
		str = str.replaceAll(" ", "");
		Iterator<Integer> it= Arrays.stream(str.split("[+,-]"))
				.map(Integer::parseInt)
				.collect(toList()).iterator();
		int result = it.next();
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i) == '+') {
				result += it.next();
			}else if(str.charAt(i) == '-') {
				result -= it.next();
			}
		}
		return result;
		
	}
}