[Java] 백준 7490 - 0 만들기

[Java] 백준 7490 - 0 만들기

문제번호: 7490(0 만들기)

풀이(java)

백트래킹을 사용해서 풀었는데 조건에 부합하는지 판정하는 부분이 조금 난잡해졌다.

가장 먼저 operator배열을 -1로 초기화한 다음, 0, 1, 2의 모든 조합을 구성하고 0은 "+" 1은 " " 2는 "-"로 매핑하고 스택에 차곡차곡 담는다.

여기서 +, -는 그냥 스택에 담아버리면 되는데 " "가 온다면, 스택에서 pop을 하고 해당원소와 넣을 원소를 합친다음 다시 push한다. 그 다음 스택을 탐색하면서 원소들의 합이 0이 되는지 안되는지 확인한다.

마지막으로 0이 맞다면, 현재 operator배열의 구성이 입력값 n 사이사이에 들어가면 된다. n이 7이라고 했을 때, 1234567이라는 문자열을 만들고 사이사이 인덱스는 1부터 2씩 증가하므로 operator배열을 탐색하면서 0이면 "+" 1이면 " " 2이면 "-"를 1, 3, 5, 7 .... 인덱스에 넣어주고 해당 문자열을 출력하면 된다.

여기서 한번에 다 출력해야되므로 StringBuilder List에 담아준다음 DFS가 끝나고 한번에 출력해준다!!

줄바꿈 조심

import java.io.*; import java.util.*; public class boj_7490 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int[] operator; static int[] num; static Stack stack = new Stack<>(); static List answer = new ArrayList<>(); public static void main(String[] args) throws IOException { int n = Integer.parseInt(br.readLine()); for (int i = 0; i < n; i++) { int input = Integer.parseInt(br.readLine()); num = new int[input]; for (int j = 0; j < input; j++) { num[j] = j + 1; } operator = new int[input - 1]; Arrays.fill(operator, -1); dfs(0, input - 1, input); Collections.sort(answer); for (StringBuilder s : answer) System.out.println(s); System.out.println(); answer.clear(); } } public static void dfs (int start, int end, int input) { if (start == end) { stack.add(String.valueOf(num[0])); for (int i = 0; i < end; i++) { if (operator[i] == 0) { stack.add("+" + num[i + 1]); } else if (operator[i] == 1) { stack.push(stack.pop() + num[i + 1]); } else if (operator[i] == 2) { stack.add(String.valueOf(-(num[i + 1]))); } } int result = 0; for (String x : stack) { result += Integer.parseInt(x); } if (result == 0) { StringBuilder sb = new StringBuilder(); for (int i = 1; i < input + 1; i++) sb.append(i); int idx = 1; for (int i : operator) { if (i == 0) sb.insert(idx, "+"); else if (i == 1) sb.insert(idx, " "); else sb.insert(idx, "-"); idx += 2; } answer.add(sb); } stack.clear(); return; } for (int i = 0; i < 3; i++) { operator[start] = i; dfs(start + 1, end, input); operator[start] = -1; } } }

from http://lee-s-k.tistory.com/14 by ccl(A) rewrite - 2021-12-30 06:02:14