[백준 156630 , Java] N과 M (9)

문제

www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

 

풀이

 이 문제는 중복을 어떻게 처리할지가 관건이다. 뽑을 수 있는 숫자가 담긴, 크기가 N인 배열을 candidates라고 하자. 그리고 candidates에서 뽑은 숫자를 넣는, 크기가 M인 배열을 numArray라고 하자. 그러면 numArray에 들어갈 수 있는 숫자는 candidate의 0번째 인덱스부터 N-1인덱스 중에서 이전에 선택하지 않은 인덱스이다. 그런다음 중복된 값에 대한 처리를 해줘야한다. 예를 들어 candidates에 1 2 4 4 가 있을 때 뽑은 인덱스가 0 1 3인 경우와 0 1 4 인경우는 뽑힌 인덱스는 다 다르지만 최종 값이 같으므로 중복처리를 해줘야한다. 

 

 이를 처리하는 방법은 2가지가 있다. 

 

풀이1 - HashSet을 이용하는 경우

 재귀를 이용해서 numArray에 들어갈 수 있는 숫자를 뽑는다. 이때 뽑은 숫자의 개수가 M개인 경우 이 숫자를 HashSet에 담는다. 이때 숫자로 하게 되는 경우 출력형식을 맞출 수 없으므로 매개변수로 String을 이용한다.

 

 마지막에 숫자를 정렬해야하는데, 이때 LinkedHashSet을 이용하면 별도의 정렬을 구현하지 않아도 된다. 

 

* 처음에 StringBuffer를 이용해서 마지막 두칸을 삭제하는 것으로 구현했는데 이 경우 두가지 문제가 있다. 하나는 숫자를 삭제하지만 그 칸이 그대로 남아있다는 것이고, 1000+" " 인경우 1000+" " 을 삭제하는 것이 아니라 0+" "을 삭제한다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static int[] candidate;
    public static boolean[] isPickedIndex;
    public static LinkedHashSet<String> pickedNums;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        candidate = new int[N];
        isPickedIndex = new boolean[N];
        pickedNums = new LinkedHashSet<>();
        String numString = "";


        st = new StringTokenizer(br.readLine()," ");
        for(int index =0; index<N; index++){
            candidate[index] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(candidate);
        pickNums(0,numString);


       for(String s : pickedNums){
           bw.write(s+"\n");
       }
       bw.flush();




    }
    public static void pickNums(int count, String numString){
        if(count>=M){
            pickedNums.add(numString);
        }
        else{
            for(int index = 0 ; index<candidate.length; index++){
                if(!isPickedIndex[index]){
                    isPickedIndex[index] =true;
                    int num = candidate[index];

                    pickNums(count+1, numString+num+" ");
                    isPickedIndex[index] =false;

                }
            }
        }
    }
}

 

풀이2 - 이전 숫자를 저장

 

 백트래킹이다. numArray의 count 인덱스에 들어갈 수 있는 조건은 1) 넣으려고 하는 candidate의 index가 이전에 사용된 적이 없다 2) numArray의 count자리에 candidate[index]가 온적이 없다. 이다

 

 candidates를 정렬하게 되면 중복된 숫자가 차례로 나오기 때문에 ( 1 2 4 4) 이전 숫자만 기억하면 중복을 처리할 수 있다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static int[] candidates;
    public static int[] numArray;
    public static  boolean[] visited;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        candidates = new int[N];
        numArray = new int[M];
        visited = new boolean[N];

        st = new StringTokenizer(br.readLine());
        for(int index = 0 ; index<N; index++){
            candidates[index] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(candidates);
        pickNum(0, bw);
        bw.flush();

        br.close();
        bw.close();
    }
    public static void pickNum(int count, BufferedWriter bw) throws Exception{
        if(count>=M){
            for(int num : numArray){
                bw.write(String.valueOf(num)+" ");
            }
            bw.write("\n");
        }
        else{
            int numBefore = 0;
            for(int index = 0; index<N ;index++){
                if(!visited[index]){                                    // index에 대한 검사
                    if(numBefore!= candidates[index] || index == 0){    // 값에 대한 검사
                        visited[index] = true;
                        numBefore = candidates[index];
                        numArray[count] = candidates[index];

                        pickNum(count+1, bw);
                        visited[index] = false;
                    }
                }
            }
        }
    }
}

 

comment

 두번째 풀이가 도저히 이해가 안가서 한참 헤맸다. 이해한 내용을 한 줄로 정리하면, "numArray count 인덱스에는 candidate에서 이전에 뽑은 인덱스와 그 인덱스에 해당하는 값은 올 수 없다"