[백준] 알고리즘 분류(백트래킹,JAVA)15666번, N과 M(12)

문제 링크

15666번: N과 M (12)

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N개의 자연수 중 M개를 고른 비내림차순 중복되지 않은 수열을 구합니다.

2. 수열에서 각 값들을 띄어쓰기로 구분합니다.

3. 같은 수를 여러 번 선택이 가능합니다.

4. 수열을 사전 순 증가하는 순서의 형태로 결과를 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. N개의 자연수에서 M개를 중복 가능 및 비내림차순으로 선택한 수열을 탐색합니다.

 

3. 수열을 사전 순 증가하는 순서의 형태로 결과를 출력합니다.

 

수열 탐색!

 

수열의 값을 중복되게 선택할 수 있기 때문에 HashSet을 이용해서 입력되는 자연수 값들이 중복되지 않도록 저장합니다.

 

수열을 사전 순 증가하는 순서의 형태로 저장되기 위해서 입력되는 자연수의 값들을 오름차순으로 정렬한 뒤 탐색합니다.

 

탐색과정!

 

1) 백트래킹을 통해서 순차적으로 M개를 선택할 수 있는 수열의 모든 경우를 탐색합니다.

 

2) 수열이 완성되었을 때 LinkedHashSet에 중복되지 않도록 저장합니다.

 

3) 모든 경우 탐색한 뒤, LinkedHashSet에 대한 정보를 결과로 출력합니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

M : 1

자연수의 값

4 4 2

 

2. N개의 자연수에서 M개를 중복되지 않게 선택한 수열을 탐색합니다.

 

수열 탐색 전 오름차순 정렬!

※HashSet을 이용해서 자연수 중복을 방지하였습니다.

 

자연수 : 2 4

 

수열 탐색!

 

1) 모든 경우 탐색!

{2}, {4}

 

2) 중복되지 않도록 저장!

{2}, {4}

 

3. 수열을 사전 순 증가하는 순서의 형태로 결과를 출력합니다.

 

3) 사전 순 증가하는 순서로 결과 출력

{2}, {4}

 

2

4

결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N, M과 자연수들을 띄어쓰기 기준 나누었습니다.
• search함수를 진행하여 M개를 선택한 모든 경우의 수열을 구합니다.
• 수열이 완성되었을 때 LinkedHashSet을 이용하여 중복되지 않은 수열을 저장합니다.
• LinkedHashSet을 저장한 수열들을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해서 M개를 중복 선택하는 수열을 탐색합니다.
• search함수는 수열이 완성되었을 때 LinkedHashSet에 중복되지 않도록 저장합니다.

 

결과코드

 

import java.io.*;
import java.util.*;

public class Main{
    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(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        ArrayList<Integer> list = new ArrayList<>();	//자연수 저장 List
        st = new StringTokenizer(br.readLine()," ");
        HashSet<Integer> set = new HashSet<>();	//숫자 중복 확인 HashSet
        LinkedHashSet<String> answer = new LinkedHashSet<>();	//수열 저장 LinkedHashSet
        //입력되는 자연수 저장
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(st.nextToken());
            if(!set.contains(num)){	//중복되지 않은 자연수 일 때
                set.add(num);
                list.add(num);
            }
        }
        Collections.sort(list);	//자연수 오름차순 정렬
        search(list, answer,0,0, M, "");	//수열 모든 경우 탐색!
        //수열에 대한 정보 BufferedWriter 저장
        for(String str : answer)
            bw.write(str + "\n");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //중복 선택 가능한 모든 수열 백트래킹으로 탐색하는 함수
    static void search(ArrayList<Integer> list, LinkedHashSet<String> answer, int cur,int count, int end, String str){
        if(count == end){		//수열 완성시!
            answer.add(str);	//LinkedHashSet을 통해 중복 확인 및 저장!
            return;
        }
        //수열 탐색!
        for(int i=cur;i<list.size();i++){
            String temp = str + list.get(i);
            if(count != end - 1)
                temp += " ";
           search(list,answer,  i,count+1, end, temp);
        }
    }
}