[백준] code.plus(브루트 포스 Part 1,JAVA)16943번, 숫자 재배치

문제 링크

16943번: 숫자 재배치

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. A에 포함된 숫자를 이용하여 새로운 숫자 C를 만들어야 합니다.

2. C는 B보다 작아야 하며 0으로 시작할 수 없습니다.

3. C의 가장 큰 값을 결과로 출력합니다.

4. C를 아무것도 만들지 못하면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 만들 수 있는 모든 C를 만들어서 조건에 만족하는지 확인합니다.

 

3. 조건에 만족하는 C중에 가장 큰 값을 결과로 출력합니다.

 

C를 만들 수 없는 경우

 

B의 자릿수가 A보다 작으면 C는 존재할 수 없습니다.

 

예를 들어

A : 1234(자릿수 : 4개)

B : 578(자릿수 : 3개)

 

A를 통해 어느 C의 값을 만들어도 578보다는 클 수 밖에 없기 때문에 C를 만들 수 없습니다.

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

A : 1234B : 3456

 

2. 만들 수 있는 모든 C를 만들어서 조건에 만족하는지 확인합니다.

 

C = {1234, 1243, 1324, 1342, 1423, 2134..... 3421, .... 4321}

 

B : 3456보다 작으면서 가장 큰 값은 3421입니다.

 

3. 조건에 만족하는 C중에 가장 큰 값을 결과로 출력합니다.

 

가장 큰 값 3421을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 입력된 값을 띄어쓰기 기준 나누었습니다.
• B의 자릿수가 A의 자릿수보다 작으면 C를 존재하지 않기 때문에 -1을 BufferedWriter 저장였습니다.
• cal을 실행하여 조건에 만족하는 C의 최대값을 구해서 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 조건에 만족하는 C 중에서 최대값을 구합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Integer> A = new ArrayList<>();	//A의 숫자들 저장 리스트
    static boolean[] visited;	//해당 숫자 사용 확인 배열
    static int B, answer = -1;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        String str = st.nextToken();
        //A에 숫자들 저장
        for(int i=0;i<str.length();i++)
            A.add(Character.getNumericValue(str.charAt(i)));
        B = Integer.parseInt(st.nextToken());
        if(B / (10*A.size()) != 0){		//자릿수 확인
            visited = new boolean[A.size()];

            //C의 모든 경우에서 조건에 만족하는지 확인 및 최대값 구하기
            for(int i=0;i<A.size();i++){
                if(A.get(i)!=0){
                    visited[i] = true;
                    cal(1, A.get(i));
                    visited[i] = false;
                }
            }
        }
        bw.write(answer + "");	//최대값 BufferedWrtier 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //C의 모든 경우에 조건이 만족하는 최대값을 구하는 함수
    static void cal(int depth, int value){
        if(depth == A.size()){
            if(value < B)
                answer = Math.max(answer, value);
            return;
        }
        for(int i=0;i<A.size();i++){
            if(visited[i])
                continue;
            visited[i] = true;
            cal(depth + 1, value * 10 + A.get(i));
            visited[i] = false;
        }
    }
}