[백준/JAVA] 2529번: 부등호

🔺 문제

2529번: 부등호

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int K;
    
    static int[] nums;
    static char[] signs;
    static boolean[] used;    // 0~9 사용 여부
    
    static List<String> answer = new ArrayList<>();
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        K = Integer.parseInt(br.readLine()) + 1;
        
        nums = new int[10];
        for(int i = 0 ; i < 10 ; i++) {
            nums[i] = i;
        }      
        
        signs = new char[K - 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < K - 1 ; i++) {
            signs[i] = st.nextToken().charAt(0);
        }
        
        for(int i = 0 ; i < 10 ; i++) {
            used = new boolean[10];
            
            used[i] = true;
            back(i, 0, i+"");
            used[i] = false;
        }
        
        System.out.println(answer.get(answer.size() - 1));
        System.out.println(answer.get(0));
    }
    
    private static void back(int startIdx, int depth, String word) {
        if (word.length() == K) {
            answer.add(word);
            return;
        }
        
        for (int i = 0; i <= 9; i++) {
            if(!used[i]) {
                char tmp = signs[depth];
                
                if(tmp == '>') {
                    if(startIdx > i) {
                        used[i] = true;
                        back(i, depth + 1, word+i);
                        used[i] = false;
                    }
                }
                else {
                    if(startIdx < i) {
                        used[i] = true;
                        back(i, depth + 1, word+i);
                        used[i] = false;
                    }
                }
            }
        }
    }
}
 

✅ 해결 아이디어
✔ 백트래킹
- 주어진 부등호 조건을 만족하는 수열을 찾으면 됨.
- 조건을 만족하는 모든 수열을 list에 저장해 정렬 후, 마지막 값과 처음 값 출력

 

💥 유의사항

• 부등호 조건에 맞아야 함

 

 

---

🔺 다른 풀이들

- https://www.acmicpc.net/source/63257879

import java.util.*;
public class Main {
    static int n;
 
    static char[] a;
    static boolean[] visited;
 
    static List<String> list;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new char[n];
 
        for(int i = 0; i < n ; i++)
            a[i] = sc.next().charAt(0);
 
        visited = new boolean[10];
        list = new ArrayList<>();
 
        combi(0, "");
        Collections.sort(list);
 
        System.out.println(list.get(list.size()-1));
        System.out.println(list.get(0));
    }
 
    public static void combi(int depth, String t) {
        if(depth == n + 1) {
            list.add(t);
            return;
        }
 
        for(int i = 0 ; i < 10 ; i++) {
            if(!visited[i]) {
                if(depth == 0 || check(t.charAt(depth - 1) - '0', a[depth - 1], i)) {    // 이전 값이랑 비교
                    visited[i] = true;
                   combi(depth + 1, t + i);
                    visited[i] = false;
                }
            }
        }
    }
 
    // 이전 값이랑 비교하는 메소드
    public static boolean check(int a, char s, int b) {
        if(s == '<')
            return a < b;
        else
            return a > b;
    }
}

 

 

- 이 풀이가 이해하기 쉽고 복습하기 좋은 듯! (복습용,,,)

[백준 2529 : JAVA] 부등호 / 백트래킹

---

💬 느낀 점

백트래킹으로 풀 생각은 했는데..

실버 문제인데 조건 하나 추가되었다고 못 풀다니..

다음엔 풀어드리겠다..ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

 

[Algorithm] 백준 2529번_부등호(Java)