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

문제에서 1부터 N까지의 자연수 중 M개를 선택하는데 같은 수를 여러 번 골라도 된다 라고 되어있기때문에 1부터 N까지 M개를 오름차순으로 나열하면 된다.

문제의 출력 예제를 보면

예제 1번은
1부터 3까지 1개씩 오름차순으로 출력한것이고

예제 2번은 1부터 4까지 2개씩 오름차순으로 출력한 것이다.

* 문제의 조건

1) 1부터 N까지 자연수를 가진다.
2) M만큼의 수로 조합하여 출력을한다.
3) 숫자 중복이 가능하다.

* 재귀함수를 만들자

1부터 3(N)까지의 수에서 2(M)개를 조합해서 출력을 한다면 중복을 허용하니
1-1 , 1-2 , 1-3, 2-1 ... 이렇게 출력이 될 것이다.
N까지 출력하다가 N과 같아지면 한 자리위로 올라가 다시 N까지 출력한다.
이렇게 동작할 수 있도록 코드를 작성하면 이렇게 작성할 수 있다.

public static void dfs(int depth){
        if(depth == M){ 
            for(int i=0;i<M;i++){
            //
            }
            return;
        }
        for(int i=1;i<=N;i++){
            // 1부터 N의 수까지 출력하는 코드
        }
    }

* 전체코드

위의 재귀함수에 빈 부분에 나머지 코드를 작성하고 Main코드와 합친다면

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

public class Main{
    
    public static int[] arr;
    public static int N,M;
    public static StringBuilder str = new StringBuilder();
    
    
    public static void main(String[] args) throws IOException  {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer strT = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(strT.nextToken());
        M = Integer.parseInt(strT.nextToken());
        
        arr = new int[M];
        dfs(0);
        System.out.println(str);
    }
    public static void dfs(int num){
        if(num == M){
            for(int i=0;i<M;i++){
                str.append(arr[i]).append(' ');
            }
            str.append('\n');
            return;
        }
        
        for(int i=1;i<=N;i++){
            arr[num] = i;
            dfs(num + 1);
        }
    }   
 }

이 코드를 백준에 제출을 한다면

* 마치며

Scanner와 System.out.print로 반복출력을 하게되면 입출력에 많은 시간을 소요하게되어
시간초과를 발생시킨다. 그렇기에 StringBuilder와 BufferedReader를 사용했다.
BufferedReader는 문자열을 한줄씩 읽기 때문에 공백을 넣고 StringTokenizer를 사용하여 구분을 할 수 있도록 했습니다. 이 글을 시작으로 알고리즘쪽 글을 조금씩 써보려고 합니다. 읽어주셔서 감사합니다.