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

 

관련글

 

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

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

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

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

 

2. 풀이

 

이 문제는 백트래킹 문제이다.

이전 N과 M(2)와 유사하지만, 1~N까지의 숫자가 아니라 N개의 숫자가 10,000이하의 임의의 숫자이므로 그 숫자를 사전에 저장해두고 그 저장된 숫자를 선택하는 경우를 찾으면 된다.

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

 

 

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];
        selected = new int[m];
        check = new boolean[n];
        
        line = br.readLine().split(" ");
        for(int i=0; i < n; i++){
            nums[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(nums);
        go(0, 1);
        
        System.out.println(sb);
        br.close();
    }
    private static void go(int seq, int start){
        if(seq == m){
            for(int i : selected){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i=start; i <= n; i++){
            if(check[i-1]) continue;
            check[i-1] = true;
            
            selected[seq] = nums[i-1];
            go(seq+1, i+1);
            check[i-1] = false;
        }
    }
}

 

 

4. 다른 방법으로 풀어보기

 

이전의 N과 M(2)에서와 같이, 이 문제는 $O(N!)$에서 $O(2^N)$ 수준으로 시간복잡도를 줄일 수 있다. 그 해결 방법은 다음과 같은 코드로 작성해볼 수 있다.

 

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

public class Main{
    static int n;
    static int m;
    static StringBuilder sb;
    static int[] nums; // 10,000이하의 숫자들 저장하는 배열
    static int[] selected;
    
    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];
        line = br.readLine().split(" ");
        for(int i=0; i < n; i++){
            nums[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(nums);
        selected = new int[m];
        
        go(0, 1);
        
        System.out.println(sb);
        br.close();
    }
    
    
    // seq는 몇 개의 숫자가 선택되었는지를 알아내는 부분
    // idx는 현재 몇 번째의 숫자를 선택 / 미선택할 것인지를 채택하는 부분
    private static void go(int seq, int idx){
        if(seq == m){
            for(int i : selected){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // 아래에서 반복문이 사라진 것을 알 수 있음!
        // 이를 통해 재귀만 사용하여 해결하여 더 빠른 시간복잡도를 유지
        
        // 만약 계속 재귀를 통해 넘어가면 언젠간 n을 넘어가게 되니, 그 이후에는 바로 반환시킴
        if(idx > n) return; 
        
        // 현재 숫자를 선택하는 경우의 재귀 방식
        // 이후 다음 선택할 숫자로 넘어간다. 아래 2줄은 현재 idx 숫자를 선택하는 경우임
        selected[seq] = nums[idx-1];
        go(seq+1, idx+1);
            
        // 현재 숫자를 선택하지 않는 경우의 재귀 방식
        selected[seq] = 0;
        go(seq, idx+1);
    }
}

 

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