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

문제 분석

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

0~9의 숫자를 한 번씩만 사용하여 길이가 k+1인 숫자열을 만든다.

이때 부등호 관계를 만족해야 한다.

숫자열의 최댓값과 최솟값은?

구현 아이디어

0~9의 숫자를 하나씩 골라서 숫자 조합을 만들어야 함 -> 브루트 포스 

숫자 탐색 방법 -> dfs 재귀탐색 사용

탐색 중 해당 경로가 부등호를 만족하는지 확인 -> 백트래킹

 

• 0~9를 반복 탐색 (dfs) 
  • 숫자를 하나 고르고, 고른 숫자를 방문처리함
  • 재귀 탐색으로 다음 숫자를 고름
  • 이미 방문처리된 숫자 제외한 나머지 숫자 중에 하나 고르기
    • 수열이 부등호를 만족하는지 확인
    • 만족하는 경우에만 재귀 탐색으로 다음 숫자 고르기(백트래킹)
  • 위 과정을 반복
  • 깊이가 k가 될 때까지 반복하면 길이가 k+1인 수열이 만들어짐
  • 만들어진 수열을 list에 저장
• list에 저장된 수열을 정렬 (작은 수부터 탐색 중이니 이미 오름차순으로 정렬된 상태)
• 가장 앞에 있는 수열을 최소값, 마지막에 있는 수열을 최대값으로 출력

시간 복잡도

dfs 탐색 시 시간 복잡도는 O(10^k) k는 최대 9이므로 최악의 경우 1억번의 연산이 발생된다.

그런데 check배열과 부등호 조건을 검사하는 백트래킹에 의해 1억번 이하의 연산이 발생하게 된다.

따라서 제한 시간 안에 연산 가능하다.

알고리즘

수열의 모든 경우를 탐색하는 문제이므로, dfs 재귀탐색을 사용한 브루트 포스라고 할 수 있음

코드 설계

1. 입력값 받기
2. 길이 k+1인 수열 만들기
   1. dfs탐색으로 숫자 선택
   2. 수열이 부등호를 만족한다면 다음 숫자 고르기(재귀호출)
   3. 깊이 k가 되었다면 result 리스트에 저장
3. max, min 출력

정답 코드

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

public class Main{
    static int k;
    static char arr[];
    static boolean check[] = new boolean[10];
    static ArrayList<String> result = new ArrayList<>();

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

        for(int i=0; i<k; i++){
            arr[i] = st.nextToken().charAt(0);
        }
        for(int i=0; i<10; i++){
            check[i] = true;
            dfs(i, 0, i+"");
            check[i] = false;
        }
        System.out.println(result.get(result.size()-1));
        System.out.println(result.get(0));
    }
    static void dfs(int now, int cnt, String num){
        if(cnt==k){
            result.add(num);
            return;
        }
        for(int next=0; next<10; next++){
            if(check[next]) continue;
            if((arr[cnt]=='<'&&now<next)||(arr[cnt]=='>'&&now>next)){
                check[next] = true;
                dfs(next, cnt+1, num+next);
                check[next] = false;
            }
        }
    }
}