자바(백준) 18511 큰 수 구성하기

오답 노트 & 새로 알게 된 점

해당 문제는 전에 풀었던 카드 놓기와 비슷하지만, 카드 놓기는 중복을 제외한 순열이었다면, 이번 문제는 중복 가능한 순열이다. 그래서 if(visit[i]) continue 구문만 빼준다면 중복 가능한 순열이 된다.

똑같은 방식으로 String형으로 set에 중복 가능한 순열들을 모아놓은 뒤에 list에 Integer형으로 변환하여 저장한다. 그리고 max값을 지정하여 if 조건식을 만족하게 한 뒤 max 값을 출력하면 된다.

 

하지만 여기서 중요한 부분이 있다. 위와 같이 풀면 perm1만을 포함하는데, 여기서 반례가 생긴다.

14 2

7 8 

을 하게 되면, N은 두자리 숫자인데 값은 8이 나와야 한다. 반례가 생기는 것이다. 그래서 perm2라는 메소드를 새로 만들어 N의 숫자 자릿수 - 1을 만족하는 중복순열도 만들어준다. 그래서 perm1, perm2를 실행한 뒤 max 값을 구하면 AC가 나온다.

 

---

 

코드

package BruteForce_Search;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    static String arr[];
    static boolean visit[];
    static Set<String> set = new HashSet<>();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> al = new ArrayList<>();
        String sstr = st.nextToken();   //숫자의 길이를 알기 위해 먼저 String으로 받음
        int N = atoi(sstr);
 
        int K = atoi(st.nextToken());
 
        arr = new String[K];
        visit = new boolean[K];
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < K; i++){
            arr[i] = st.nextToken();
        }
        ///////////////////////////////////////////////////////입력 끝
 
        perm1("", 0, sstr.length());
        perm2("", 0, sstr.length() - 1);
 
        for(String ss : set){
            al.add(atoi(ss));
        }
 
        int max = Integer.MIN_VALUE;
 
        for(int i = 0; i < al.size(); i++){
            int value = al.get(i);
            if(value >= max && value <= N) max = value;
        }
        System.out.print(max);
    }
    //같은 자리 숫자일 때
    static void perm1(String str, int count, int limit){
        if(limit == count){
            set.add(str);
            return;
        }
        for(int i = 0; i < arr.length; i++){
 
            visit[i] = true;
            perm1(str + arr[i], count + 1, limit);
            visit[i] = false;
        }
    }
 
    // 자리 수 - 1 까지 해줘야함.
    static void perm2(String str, int count, int limit){
        if(limit  == count){
            set.add(str);
            return;
        }
        for(int i = 0; i < arr.length; i++){
            visit[i] = true;
            perm2(str + arr[i], count + 1, limit);
            visit[i] = false;
        }
    }
}