[DFS] - S1_2529_부등호

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

2529번: 부등호

 

코딩테스트 언어를 python에서 java를 바꾸는 과정에서 문제들의 유형들을 여러가지 풀어봐야할 것 같아서 DFS 문제로 정하고 문제를 품

 

📌 - 처음 생각한 풀이

1. DFS로 완전탐색을 하면서 부등호에 맞는 모든 경우의 수를 List에 저장
2. list의 크기가 N+1이 됐을 때, 리스트에 있는 모든 값들을 str에 순차적으로 저장
3. str을 long으로 형변환 하면서 크기 비교 -> 최솟값과 최댓값 비교해서 저장

이렇게 풀이를 하니까 예외처리를 해줘야할 것들이 많이 생겨서 코드가 점점 복잡해지고, 가독성이 많이 떨어졌다.

DFS의 매개변수도 부등호 배열의 인덱스 값을 넣어주다보니 코드를 작성하면서도 스스로가 헷갈려서 시간을 더 잡아 먹은것 같다.

물론 정답으로 통과는 했지만 만족할만한 풀이가 아니기에 다른 분의 코드를 참고해서 다시 문제를 해결해봤다.

 

 

👉 - java code

package DFS.S1_2529_부등호;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static int N;
    public static long min = Long.MAX_VALUE,max = Long.MIN_VALUE;
    public static String[] arr;
    public static String minStr,maxStr;
    public static ArrayList<String> result = new ArrayList<>();
    public static boolean[] visited;
    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        arr = new String[N+1];
        visited = new boolean[10];
        st = new StringTokenizer(br.readLine());
        for ( int i = 0;i<N;i++){
            arr[i] = st.nextToken();
        }

        DFS(0,result);

        System.out.println(maxStr);
        System.out.println(minStr);


    }

    public static void DFS(int s,ArrayList<String> list){
        if (list.size() == N+1){
            String ans="";
            for(String t : list){
                ans+=t;
            }
            if (min> Long.parseLong(ans)){
                min = Math.min(Long.parseLong(ans),min);
                minStr = ans;
            }

            if (max <Long.parseLong(ans)){
                max = Math.max(Long.parseLong(ans),max);
                maxStr = ans;
            }
            return;
        }


        for (int i =0;i<10;i++){
            boolean mis = false;
            if (list.size() ==0){
                mis = true;
            }
            if (!visited[i]){
                    if(s >0){
                        switch (arr[s-1]){
                            case "<":
                                if(Integer.parseInt(list.get(list.size()-1)) < i){
                                    mis = true;
                                }
                                break;
                            case ">":
                                if(Integer.parseInt(list.get(list.size()-1)) >i){
                                    mis = true;
                                }
                                break;
                        }
                    }
                    if(mis){
                        visited[i] = true;
                        list.add(String.valueOf(i));
                        DFS(s+1,list);
                        visited[i] = false;
                        list.remove(list.size()-1);
                    }

            }

        }


    }

}

 

 

📌 - 참고해서 다시 만든 코드

1. 모든 경우의 수를 DFS로 돌면서 조건에 부합하면서 길이가 N+1이 됐을 때 ArrayList에 추가한다.
2. 추가된 숫자들을 sort해서 최댓값과 최솟값을 구한다.

확실히 너무 쉽게 짤 수 있는 문제였고, 이런 방법을 생각 못해서 아쉽지만 그래도 배웠다고 생각하며 기록을 한다.

package DFS.S1_2529_부등호;

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

public class Main2 {
    public static int N;
    public static String[] arr;
    public static ArrayList<String> result = new ArrayList<>();
    public static boolean[] visited = new boolean[10];

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        arr = new String[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = st.nextToken();
        }

        DFS( "",0);
        Collections.sort(result);
        System.out.println(result.get(result.size() - 1)); //최댓값
        System.out.println(result.get(0)); //최솟값


    }

    public static void DFS( String str,int depth) {
        if (depth == N + 1) {
            result.add(str);
            return;
        }

        for (int i = 0; i < 10; i++) {
            if (depth == 0 || !visited[i] && compare(str.charAt(str.length()-1)-'0',i,arr[depth-1])) {
                visited[i] = true;
                DFS(str+i,depth+1);
                visited[i] = false;

            }

        }


    }
    private static boolean compare(int a, int b, String c) {
        if (c.equals("<")) return a < b;
        else return a > b;
    }

}