코드트리 [자바 java] k개 중에 1개를 n번 뽑기

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 두 수가 주어지면 차례대로 순열을 만들어서 출력하는 프로그램이다.

알고리즘 풀 때 많이 사용되는 개념인데, 매번 풀 때마다 헷갈리는 것 같다. 

문제의 조건에 따라 따져야 할 것이 많은데, 이 문제는 중복을 허용하고, 오름차순, 내림차순에 대한 기준이 없다. 따라서 재귀함수에서 for문을 돌 때 현재 i의 값을 넘겨주지 않아도 되고(오름, 내림 x) , 현재 탐색하고 있는 i값의 방문여부도 상관하지 않아도 된다.

 

처음에 StringBuilder을 사용하지 않아서 시간초과가 나왔는데, 수정하니 정상적으로 작동했다.

 

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




public class Main {

    
static int[] arr;
static int m;
static int n;
static StringBuilder sb;

static void print(){
    for(int i = 0;i<m;i++){
        sb.append(arr[i]).append(" ");
    }
    sb.append("\n");
}

static void make(int size){
    if(size == m){
        print();
    }

    else{
        for(int i = 1;i<= n;i++){
         
                arr[size] = i;
                make(size+1);
          

      }
    }
    
}


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        sb = new StringBuilder();

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

        arr = new int[m];

        make(0);

        System.out.println(sb);

    }
}