[백준] 2529번 부등호 JAVA (자바) 풀이

문제 2529번 (백트래킹)

 

 :  부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다

    부등호 기호 앞 뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다

    숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다

 

 :  부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있다

    부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다

 

 

 [입력]

 :  첫 줄에 부등호 문자의 개수 정수 k

 :  그 다음 줄에는 k개의 부등호 기호 (k의 범위는 2 ≤ k ≤ 9)

 

 

 [출력]

 :  k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (첫 자리가 0인 경우도 정수에 포함)

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 

 

 조건1  부등호 조건에 충족하지 않는다면 다시 되돌아가 시작 노드를 변경해 백트래킹 실행 

 

 종료 조건) count==K

 count가 K가 되면 K개의 숫자를 모두 뽑았기 때문에 종료하고 result에 문자 추가한다

 

 1. 시작지점은 for문을 통해 0 ~ 9까지 넣고 now로 받는다

 시작 지점인 now를 0 ~ 9 에서 순차적으로 dfs 돌리고 next를 정한다

 초기 시작 지점은 i로 int지만 dfs 인자는 String 이므로 +"" 를 붙여서 문자열로 변경한다

 

 2. 다음지점은 if문 조건 기준으로 충족해야 추가된다

• '<' 일 경우) 현지점 < 다음지점
• '>' 일 경우) 현지점 > 다음지점  
  
  

 3. 결과 문자들을 정렬하지 않아도 상관없다

 애초에 앞글자부터 i를 0부터 넣으면서 순차적으로 늘리기 때문에

 당연히 처음 저장되는 문자가 제일 작고 가장 나중에 저장되는 문자가 제일 크다                     

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int K;
    static char arr[];
    static boolean visit[] = 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++){
            visit[i] = true;
            dfs(i,0,i+"");
            visit[i] = false;
        }
        
        System.out.println(result.get(result.size()-1));
        System.out.println(result.get(0));
    }
    
    static void dfs(int now, int count, String number){
        if(count==K){
            result.add(number);
            return;
        }
        
        for(int next=0; next<10; next++){
            if(!visit[next]){
                if((arr[count]=='<'&&now<next)||(arr[count]=='>'&& now>next)){
                    visit[next]=true;
                    dfs(next,count+1,number+next);
                    visit[next]=false;
                }
            }
        }
    }
}

 

 [해설]
     

 :  static int K;
    static char arr[];
    static boolean visit[] = new boolean[10];
    static ArrayList<String> result = new ArrayList<>();
    

 :  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++){  초기 시작지점
            visit[i] = true;  방문처리
            dfs(i,0,i+"");  초기시작지점, count, 누적 문자열
            visit[i] = false;  초기시작지점 변경하려면 방문 취소
    }
        
 :  System.out.println(result.get(result.size()-1));  최대값
    System.out.println(result.get(0));  최소값
    
    
 :  static void dfs(int now, int count, String number){
        if(count==K){  종료조건) count가 K개면 숫자 다 뽑음
            result.add(number);  지금까지 누적 문자들 result에 추가하기
            return;
        }
        
        for(int next=0; next<10; next++){  다음지점 구하기
            if(!visit[next]){  방문전이라면
                if((arr[count]=='<'&&now<next)||(arr[count]=='>'&& now>next)){  조건 충족하면
                    visit[next]=true;  방문처리
                    dfs(next,count+1,number+next);  다음 숫자를 기준으로 다시 dfs
                    visit[next]=false;  만족하는게 없을 경우는 방문처리 취소하고 다른 숫자로 재시작
                }
            }
        }
   }


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *