알고리즘 풀이 - 백준 15654(N과 M(5), 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조
백트래킹 관련 포스팅은 여기를 참조

관련 문제인 N과 M(1)은 여기를 참조
관련 문제인 N과 M(2)는 여기를 참조
관련 문제인 N과 M(3)은 여기를 참조
관련 문제인 N과 M(4)는 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

이 문제는 N과 M(1)과 같은데 숫자가 1부터 N까지가 아니라 10,000보다 작은 임의의 서로 다른 숫자 N개가 주어진다.

그 중 중복 없이, M개를 골라 사전 순으로 출력한다.

 

 

2. 풀이

 

이전의 N과 M(1)과 동일하게 풀면 되는데, 이번에는 그 숫자가 임의의 서로 다른 숫자로 주어지게 되므로 그 숫자들을 사전에 저장하고 출력 시에 저장된 숫자의 index를 기반으로 출력하면 된다.

 

N과 M(1)은 상단의 링크 혹은 여기를 참조

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int m;
    static int[] nums;
    static int[] selected;
    static boolean[] check;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        nums = new int[n];
        check = new boolean[n];
        selected = new int[m];
        
        line = br.readLine().split(" ");
        for(int i=0; i < n; i++){
            nums[i] = Integer.parseInt(line[i]);
        }
        
        // 숫자를 미리 정렬시킴
        Arrays.sort(nums);
        
        go(0);
        
        System.out.println(sb);
        br.close();
    }
    
    private static void go(int seq){
        if(seq == m){
            for(int i : selected){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // N과 M(1)과 동일하게 수행
        for(int i=1; i <= n; i++){
            if(check[i-1]) continue;
            check[i-1] = true;
            selected[seq] = nums[i-1];
            go(seq+1);
            check[i-1] = false;
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.