[백준] code.plus(브루트포스-재귀,JAVA)2529번, 부등호

문제 링크

2529번: 부등호

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에 핵심은

1. 부등호에 맞는 숫자 중 최소값과 최대값을 구해야 한다.

2. 각 숫자는 한 번 밖에 사용하지 못한다.

3. 0~9까지 숫자를 사용할 수 있습니다.

4. 문자열 형태로 출력하여 첫 자리가 0인 경우도 포함하여 출력해야 한다.

 

배열

inequality  : 입력되는 부등호를 순서대로 저장하는 배열

 

check : 0~9까지 숫자가 사용되었는지 확인하는 배열

 

 

위에 inequality, check와 재귀를 통해 부등호에 만족하는 최대값, 최소값을 구하였습니다.

 

재귀를 통해 <, >의 조건을 만족하면 재귀를 통해 계속 탐색하고 만족하지 못한다면  다른 숫자로 탐색을 진행하여모든 탐색이 종료된 후 최대값과 최소값을 출력합니다.

 

만약 < < > 일 때

0< 2 < 3 > 1 = 탐색 완료

3 < 4 < 6 > 7 = 탐색 중단

3 < 7 < 5 = 탐색 중단

5 < 4 = 탐색 중단

 

문제에 해결알고리즘은

1. 배열 inequality를 입력값으로 초기화한다.

2. 재귀를 통해 모든 경우의 수를 구한다.

3. 모든 경우의 값을 비교하여 최소값과 최대값을 구하고 결과로 출력한다.

 

※ 0~9까지 모두 사용하여 최대값을 비교할 때에는 int 범위를 벗어나기 때문에 long을 사용해주셔야 합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 inequality배열을 초기화하였습니다.
• 부등호에 만족하는 모든 숫자의 최대값, 최소값을 구하는inequalityCal 함수를 만들었습니다.
• BufferedWriter에 부등호에 만족하는 값 중 최대값과 최소값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• inequalityCal는 재귀와 부등호의 조건을 사용하여 최대값과 최소값을 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int k;
	public static long max = Long.MIN_VALUE, min = Long.MAX_VALUE;	//최대,최소값
	public static String strMax,strMin;		//최대,최소값 문자열
	public static char[] inequality;		//부등호 저장 배열
	public static boolean[] check = new boolean[10];	//0~9 숫자 사용 확인 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화--------
    	k = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	inequality = new char[k];
    	for(int i=0;i<k;i++) {
    		inequality[i] = st.nextToken().charAt(0);
    	}
        //-------시작 값 0~9 함수 실행--------
    	for(int i=0;i<10;i++) {
    		check[i] = true;
    		inequalityCal(1, i+"");
    		check[i] = false;
    	}
    	bw.write(strMax + "\n" + strMin);		//최대값, 최소값 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //-------부등호에 만족하는 최대값,최소값 찾는 함수-----------
    public static void inequalityCal(int depth, String cur) {
    	if(depth==k+1) {
    		long temp = Long.parseLong(cur);
    		if(temp > max) {	//최대값 구하기
    			max = temp;
    			strMax = cur;
    		}
    		if(temp < min) {	//최소값 구하기
    			min = temp;
    			strMin = cur;
    		}
    		return;
    	}
    	for(int i=0;i<=9;i++) {
    		if(!check[i]) {	//숫자를 사용하지 않았을 경우
            	//부등호 조건에 만족하는지 확인
    			if((inequality[depth-1]=='<' 
                	&& Character.getNumericValue(cur.charAt(depth-1))<i) 
                	|| (inequality[depth-1]=='>' 
                    	&& Character.getNumericValue(cur.charAt(depth-1))>i))
                {
    				check[i] = true;
    				inequalityCal(depth+1, cur+i);
    				check[i] = false;
    			}
    		}
    	}
    	return;
    }
}