[백준15651] N과 M (3) / Java

TITLE

문제주소 :www.acmicpc.net/problem/15651

 

---

<문제 설명>

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

예제 입력 3

3 3

예제 출력 3

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

<풀이법>

▒ 한줄 개념: 출력 시간 중요! ▒

2021/01/05 - [Baekjoon] - [백준15650] N과 M (2) / Java

2021/01/05 - [Baekjoon] - [백준15649] N과 M (1) / Java

 

백트래킹 알고리즘의 세 번째 기본문제입니다.

개념자체는 여태 했던 다른 백트래킹 알고리즘 문제들보다 훨씬 쉬웠지만, 이 문제의 핵심은 출력 속도에 있습니다.

저는 Java를 이용하여 풀었는데, Java의 기본 출력인 System.out.println()의 경우 출력 속도가 너무 느려 테스트를 통화하지 못하였습니다.

그에 따라 BufferedWriter와 StringBuilder를 이용하여 출력을 하는 방법을 고민하였고, 최종적으로 속도가 가장 빠른 BufferedWriter를 이용하여 테스트에 통과하였습니다.

 

모든 출력함수에 대한 속도 확인: www.acmicpc.net/blog/view/57

 

<코드(Java)>

package Baekjoon;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class N_and_M_3_15651 {
    static BufferedWriter buf = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] array = new int[M];

        search(0, array, N);
        try {
            buf.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static void search(int count, int[] array, int N) {
        try {
            if (count == array.length) {
                for(int a :array){
                        buf.append(a+" ");

                }
                buf.write("\n");
            } else {
                for (int i = 0; i < N; i++) {
                    array[count] = i+1;
                    search(count+1,array, N);
                }
            }
            } catch (IOException e) {
                e.printStackTrace();
        }
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest