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

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

자연수 N, M이 주어질 때, 1 ~ N까지 자연수 중 중복 없이 M개를 고른 것을 사전 순으로 모두 출력하는 문제

 

 

2. 풀이

 

이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조)

 

N, M이 주어질 때, 중복하지 않도록 수를 고르고 사전 순으로 고른다는 것은 M개의 숫자로 이루어진 모든 부분 집합을 구하라는 의미이다.

여기서 몇 가지 해결을 위한 단서를 파악할 수 있다.

① 숫자를 M개 골랐다면 그 숫자를 출력해야 한다.
② 이미 고른 숫자를 다시 선택하지 않도록 구현해야 한다.
③ 사전 순으로 출력해야 하므로 1부터 N까지의 반복문을 사용하는 것이 좋다.

 

여기서, ①에 따라 우리는 숫자를 M개 고를 때까지 저장할 별도 공간을 마련하는 것이 좋다. 그렇지 않으면 불 필요한 상황에 출력될 수 있다.

②에 따라, 논리 배열을 생성하여 현재 숫자가 이미 선택되었는지 체크해야 하며, 완료 후에는 다시 선택할 수 있음을 설정해야 한다는 것을 알 수 있다.

 

이 문제의 시간복잡도는 N개의 숫자 중 M개를 선택하여 출력하므로 N x (N-1) x (N-2) x ... x (N-M+1) 까지 N부터 N보다 작은 M개의 숫자를 모두 곱한 것이 된다.

따라서 시간복잡도는 O(N!)이 된다.

코드를 통해 확인하는 것이 더욱 직관적이므로 코드를 확인하자.

 

 

3. 코드

 

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

 

import java.io.*;

public class Main{
    static int n;
    static int m;
    static boolean check[];  // 숫자가 선택되었는지 여부 파악하는 배열
    static int nums[];       // M개의 숫자를 저장할 배열
    static BufferedWriter bw;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        check = new boolean[n];
        nums = new int[m];
        go(0);
        
        bw.flush();
        br.close();
    }
    
    private static void go(int seq) throws IOException{
        // M개가 선택되었다면 출력 후 되돌아간다.
        if(seq == m) {
            for(int i : nums){
                bw.write(String.valueOf(i) + " ");
            }
            bw.write("\n");
            return;
        }
        
        // 1부터 시작하여 n까지 체크하되 이미 선택된 숫자면 넘어가고
        // 선택되지 않은 숫자라면 차례대로 저장한 뒤,
        // 다음 seq를 +1 하여 M과 비교하며 다음 단계로 넘어간다.
        // 이후, 출력이 완료되면 백트래킹을 통해 기 선택된 숫자를 다시 선택 가능으로 설정하고
        // 반복문을 계속 진행한다.
        for(int i=1; i <= n; i++){
            if(check[i-1]) continue;
            check[i-1] = true;
            nums[seq] = i;
            go(seq+1);
            check[i-1] = false;
        }
    }
}

 

 

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