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

<코드>

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

<풀이>

1. 어떤 접근으로 문제를 접근하려고 했는지

    중복순열의 모든 경우의 수를 출력하는 문제이다.

    다른 N과 M 문제와 다르게 단순하게 그냥 재귀함수로 숫자를 넣고 재귀함수가 끝날 때 숫자를 제거하면 되는 문제이다.

    

2. 문제를 해결하기 위한 기능

    중복순열 구하는 기능

    선택한 숫자 출력기능

 

<코드>

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

public class Main {

    public static int n, m;
    public static ArrayList<Integer> arrayList = new ArrayList<>();
    public static StringBuilder sb = new StringBuilder();

    public static void print() {
        for(int i = 0; i < arrayList.size(); i++) {
            sb.append(arrayList.get(i)).append(" ");
        }
        sb.append("\n");
    }
    public static void dfs(int h) {
        if(h == m + 1) {
            print();
            return;
        }
        for(int i = 1; i <= n; i++) {
            arrayList.add(i);
            dfs(h + 1);
            arrayList.remove(arrayList.size() - 1);
        }

    }

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dfs(1);

        System.out.println(sb);

    }
}

 

 

<후기>

System.out.println()으로 출력할 경우 타임아웃이 발생했다. 아무래도 문자열을 많이 더할수록 System.out.println()의 속도가 느리기 때문이라고 생각했고 앞으로는 StringBuilder를 적극적으로 사용해야겠다는 생각을 했다.