[99클럽 코테 스터디 37일차 TIL] 부등호 - Java [자바][백준]

 

📜 문제 내용

 

🤔 과정

• 백트래킹으로 숫자 비교를 하면서 진행한다. 
• 숫자 사용 여부의 Boolean 배열 used, 부등호가 담긴 String 배열 signs 을 생성해 확인하면서 진행. 

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

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

public class Main {
    public static int k;
    public static String[] signs;
    public static boolean[] used = new boolean[10];
    public static List<String> result = new ArrayList<>();

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

        k = Integer.parseInt(br.readLine());
        signs = new String[k];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<k;i++){
            signs[i] = st.nextToken();
        } // 입력 끝

        dfs("", 0);
        
        // 결과 배열 정렬 후 최댓값과 최솟값 출력 
        Collections.sort(result);
        System.out.println(result.get(result.size() - 1) + "\n" + result.get(0));

    }// main

	// 백트래킹 
    public static void dfs(String num, int depth) {
        if(depth == k + 1){
            result.add(num);
            return;
        }

        for(int i = 0; i < 10; i++){
            // 아직 사용하지 않은 숫자라면, 
            if(!used[i]){
                // 첫 비교이거나, 비교가 올바르다면, 
                if(depth == 0 || compareNums(num.charAt(depth - 1) - '0', i, signs[depth - 1])){
                    used[i] = true; // 방문처리
                    dfs(num + i, depth + 1);
                    used[i] = false; // 방문취소
                }
            }
        }

    }
    
    // 숫자 비교 
    public static boolean compareNums(int a, int b, String sign){
        if(sign.equals("<")){
            return a < b;
        } else {
            return a > b;
        }
    }
}

 

 

🔗 문제 링크

• 백준 - 부등호 (링크)