자바 - 백준 15651 / N과 M (3)

백준 15651 N과 M (3)
실버3

구현 방법

1 <= 선택 횟수, 뽑을 수 있는 최대 숫자 <= 7
범위임으로 한 횟수마다 뽑을 숫자를 모두 고려하면 7^7 정도 나옴으로 시간초과는 걱정안해도 됩니다.
시간 복잡도 : O((선택 횟수) ^ (뽑을 수 있는 숫자 범위))

1. 선택 횟수를 행으로, 뽑을 수 있는 최대 숫자를 열로 하는 이차원 boolean 배열을 만듭니다.
2. 재귀를 이용하여 한 재귀당 한 숫자를 뽑아서 이차원 배열에 저장합니다.
3. 선택을 다 한 경우 이차원 배열을 통해 출력합니다.

이렇게 구현했는데 시간이 좀 느려서 다른 코드를 참조했습니다.
제 코드와 비교해 보니 굳이 이차원 배열까지 만들 필요 없었습니다.
일차원 배열을 선택 횟수만큼 만들고 선택된 숫자를 넣어서 구현하면 출력시 도는 횟수가 줄어 시간이 좀 더 빨라 졌습니다.

코드

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

/**
 * 백준 15651
 * N과 M (3)
 * 실버3
 * https://www.acmicpc.net/problem/15651
 */
public class Boj15651 {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        pick(new boolean[M][N + 1], N, M, 0);

        System.out.print(sb);
    }

    public static void pick(boolean[][] visited, int n, int m, int cnt) {
        if(cnt == m) {
            for(int i = 0; i < m; i++) {
                for(int j = 1; j < n + 1; j++)
                    if(visited[i][j])
                        sb.append(j).append(" ");
            }

            sb.append("\n");

            return;
        }

        for(int i = 1; i < n + 1; i++) {
            if(visited[cnt][i])
                continue;

            visited[cnt][i] = true;
            pick(visited, n, m, cnt + 1);
            visited[cnt][i] = false;
        }
    }
}