[백준] 2529 부등호 (Java)

백준 2529 부등호 (Java)

 

출처

www.acmicpc.net/problem/2529

 

 

유형

브루트포스(완전 탐색), 백트래킹

 

배운점

• br.readLine() -> charArray

char[] cArray = br.readLine().toCharArray();

• 처음에 "< > > < <" 이 부등호 줄을 입력받을 때 위 처럼 구현을 했는데, 그렇게 되면 cArray에는 ' ' 공백까지 포함되어서 저장되어버린다.
  • 어쩐지 로직은 아무리봐도 맞는데 안되더라
• 디버깅하면서 알았음
• br.readLine()으로 입력을 받아서 charArray로 변경하고 싶을 때는 공백을 먼저 없애준 후에 toCharArray()를 사용하자

char[] cArray = br.readLine().replace(" ", "").toCharArray();

 

 

느낀점

• 백트래킹을 구현할 때는 조건 설정부터 생각을 하자 
  • 어떤 조건일 때 실행을 할 것이고 어떤 조건일 때 넘어갈 것인지
  • 재귀가 다시 돌아왔을 때 어떤 로직을 수행할 것인지
• 이전 문제인 꽃길을 풀면서 백트래킹 구현에서 먼저 생각해야할 점은
  • 재귀를 끝내는 조건
  • 참일때 어떤 로직을 수행할 것인지
  • 거짓일때는 어떤 로직을 수행할 것인지
  • 호출이 끝났을 때 visited[i] = false; 라던지 되돌려줘야할 부분이 있는지
• 이라고 생각했고, 이를 토대로 backTracking 함수의 인자부터 생각하면서 구현하니까 구현할 수 있었다.

 

• 처음으로 직접 구현해본 백트래킹이라서 매우매우 매우 뿌듯했다 ~! 할 수 있다 !

 

정리

• 완전 탐색을 해야한다고 판단이 되면 백트래킹을 고려하고, 이때 조건 설정을 잘 따져보자

import java.io.*;
import java.util.*;

public class boj2529 {

    private static int n;
    private static char[] cArray;
    private static List<String> temp;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        cArray = br.readLine().replace(" ", "").toCharArray();

        List<Integer> list = new ArrayList<>();
        temp = new ArrayList<>();
        visited = new boolean[10];

        backTracking(0, list);

        System.out.println(temp.get(temp.size()-1));
        System.out.println(temp.get(0));


    }

    private static void backTracking(int len, List<Integer> list) {
        if(len == n+1) {
            StringBuilder sb = new StringBuilder();
            for(int elem: list) {
                sb.append(elem);
            }
            temp.add(sb.toString());
        }
        else {
            if(len == 0) {
                for(int i = 0; i < 10; ++i) {
                    add(i, list);
                    backTracking(list.size(), list);

                    clear(i, list);
                }
            }
            else {
                char c = cArray[len-1];
                for(int i = 0; i < 10; ++i) {

                    if(c == '<') {
                        if(!visited[i] && list.get(list.size()-1) < i) {
                            add(i, list);
                            backTracking(list.size(), list);

                            clear(i, list);
                        }
                    } else if (c == '>'){
                        if(!visited[i] && list.get(list.size()-1) > i) {
                            add(i, list);
                            backTracking(list.size(), list);

                            clear(i, list);
                        }
                    }
                }
            }
        }
    }

    private static void add(int idx, List<Integer> list) {
        list.add(idx);
        visited[idx] = true;
    }

    private static void clear(int idx, List<Integer> list) {
        list.remove(list.size()-1);
        visited[idx] = false;
    }
}