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

문제 링크

 

15663번: N과 M (9)

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

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

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

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

 

알고리즘 진행 순서.

 

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

 

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

 

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

 

수열 탐색!

 

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

 

탐색과정!

 

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

 

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

 

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

 

예제입력 1.

 

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

 

N : 3

M : 1

자연수의 값

4 4 2

 

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

 

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

 

자연수 : 2 4 4

 

수열 탐색!

 

1) 모든 경우 탐색!

{2}, {4}, {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> num = new ArrayList<>();	//자연수 저장 리스트
        LinkedHashSet<String> set = new LinkedHashSet<>();	//완성된 수열 저장 LinkedHashSet
        boolean[] visited = new boolean[N];	//자연수 사용 확인 배열
        st = new StringTokenizer(br.readLine()," ");
        //입력되는 자연수 저장
        for(int i=0;i<N;i++)
            num.add(Integer.parseInt(st.nextToken()));
        Collections.sort(num);		//자연수 오름차순 정렬!
        //M개를 선택한 모든 수열의 경우 탐색!
        search(visited, num, set, 0, M, N, "");
        //LinkedHashSet에 저장된 수열을 BufferedWriter 저장
        for(String key : set)
            bw.write(key + " \n");

        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //M개를 선택하는 수열의 모든 경우를 탐색하는 함수
    static void search(boolean[] visited, ArrayList<Integer> num, HashSet<String> set, int cur, int end,int size, String str){
        if(cur == end){		//수열 완성!
            set.add(str);		//LinkedHashSet으로 중복되지 않는 수열을 저장!
            return;
        }
        //수열 만들기 진행!
        for(int i=0;i<size;i++){
            if(!visited[i]){
                visited[i] = true;
                String temp;
                if(cur == end-1)
                    temp = str +  num.get(i);
                else
                    temp = str + num.get(i) + " ";
                search(visited, num, set, cur+1, end, size, temp);
                visited[i] = false;
            }
        }
    }
}