[ 백준/BOJ ][JAVA] 15651 - N과 M(3)

문제

15651번: N과 M (3)

 

📒 문제

자연수 N과 M이 주어질 때, 1~N까지의 자연수 중 M개를 고른 수열을 구하라. 중복은 가능!

 

📒 풀이방식

백트래킹 기본문제

 

📒 소스코드

package BOJ.BackTracking;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class boj15651_NandM3 {
    static int M, N;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];

        solution(0);
        System.out.println(sb);
    }

    static void solution(int cnt) throws IOException {
        if (cnt == M) {

            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i] + " ");
            }
            sb.append('\n');
            return;
        }

        for (int i = 1; i <= N; i++) {
            arr[cnt] = i;
            solution(cnt + 1);
        }

    }
}

 

📒 리뷰

16561 내제출

 

---

시간 초과가 자꾸 떴었다. 처음엔 시간을 제대로 확인 안 하고 백트래킹 안에서 출력했기 때문이었고,

두 번째에는 BufferedWriter을 사용해서 출력했지만 시간 초과가 떴다

후에 StringBuilder에 넣었다가 출력해내는 형식을 사용해서 통과했다. 

둘 다 속도 차이가 그렇게 많이 나지는 않지만 StringBuilder가 조금 더 빠르다고 한다!😎😎