[BaekJoon] 7490 0 만들기 (java)

🔗 문제 링크

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

👨🏻‍💻 내가 작성한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int number;
		
		for (int i=0; i<n; i++) {
			number = Integer.parseInt(br.readLine());
			dfs(number, 1, 1, 1, 0, "1");
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	// DFS로 내려갈 때마다 각각의 String을 가져야해서 StringBuilder가 아닌 String사용
	static void dfs(int max, int now, int num, int sign, int sum, String str) {
		if(max == now) {
			sum = sum + (num * sign);
			if (sum == 0) {
				sb.append(str +"\n");
			}
			return;
		}
		dfs(max, now+1, num*10+(now+1), sign, sum, str+ " " +String.valueOf(now+1)); 
		// 빈칸인 경우 뒤의 수와 이어야 하기에 sign은 그대로 가져간다.
		dfs(max, now+1, now+1, 1, sum + (num*sign), str+ "+" +String.valueOf(now+1));
		dfs(max, now+1, now+1, -1, sum + (num*sign), str+ "-" +String.valueOf(now+1));
		
		
	}
	


}

📝 정리

문제 풀이 경험이 많이 부족해서 문제를 읽고 recursive하게 풀어야겠다~라는 생각은 했어도 DFS문제라는 것을 알아차리는데는 많은 시간이 걸린 것 같다.. 또한 String연결과 +,-가 아닌 빈칸이 들어왔을 때의 연산을 처리하는 것도 방법이 떠오르지 않아 많은 시간이 걸렸던 것 같다😥😥

String의 경우는 처음에 String+String연산은 새로운 메모리 공간을 생성하여 결과값을 저장하는 것이라 메모리 효율에 좋지 않다 생각하여 StringBuilder를 사용하려고 하였다. 하지만 또 StringBuilder를 사용하자니 메모리 주소를 공유하기에 한 곳에서 변경하면 다른 계산에서 사용할 StringBuilder의 값도 변하여 사용이 적합하지 않다는 것을 깨닫고 많은 시간을 생각하다가 결국 String을 사용하게 되었다.

사실 DFS를 하며 가지를 늘려갈때마다 새로운 문자열을 생성해야해서 String을 사용하는게 문제가 되지 않는 것인데 메모리 효율성을 높이는데 눈이 멀어 잘못된 생각을 했던것 같다.

아무튼... 여러 문제를 풀며 실력을 계속 키워야겠다🔥