[문제 풀이] 백준 15656번 N과M(7) JAVA

문제

  문제접근 방법   

해당 문제는 N과 M이 주어졌을 때 N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 프로그램을 작성하는 문제로 같은 수를 여러 번 골라도 된다. 문제를 읽고 N과 M(3)와 거의 똑같은 풀이라는 것을 알 수 있었다.

N과 M(3)에서는 N개의 숫자를 따로 입력 받지는 않지만 해당 문제에서는 문제를 입력받아 정렬 후 탐색한다는 차이점만이 

존재했다. 

< 최종 코드 >

import java.util.*;

public class Main{
    public static int num[];
    public static StringBuilder sb=new StringBuilder();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        int arr[]=new int[n+1];
        num=new int[m];
        
        for(int i=1;i<=n;i++){
            arr[i]=s.nextInt();
        }
        Arrays.sort(arr);
        dfs(0,n,m,arr);
        System.out.println(sb);
    }
    
    public static void dfs(int depth,int n,int m,int arr[]){
        if(depth==m){
            for(int i=0;i<m;i++){
                sb.append(num[i]).append(" ");
            }sb.append("\n");
            return;
        }
        for(int i=1;i<=n;i++){
            num[depth]=arr[i];
            dfs(depth+1,n,m,arr);
        }
    }

}

N과M (3)에서와 같이 본 문제에서도 방문처리를 별도로 해줄 필요가 없었다. 여기서 중요한 점은 별도의 방문처리가 없어 재귀의 호출 수가 증가하게 되어 위처럼 StringBuilder를 활용하는 것이 아니라 아래처럼 System.out.print()를 사용하면 자바에서 출력횟수가 10만을 넘어가게 되면 1초 안에 해결이 힘들어져 시간초과가 발생할 수 있다는 점을 고려해야한다.

 

< 시간 초과 발생 코드 >

import java.util.*;

public class Main{
    public static int num[];
    //public static StringBuilder sb=new StringBuilder();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        int arr[]=new int[n+1];
        num=new int[m];
        
        for(int i=1;i<=n;i++){
            arr[i]=s.nextInt();
        }
        Arrays.sort(arr);
        dfs(0,n,m,arr);
       
    }
    
    public static void dfs(int depth,int n,int m,int arr[]){
        if(depth==m){
            for(int i=0;i<m;i++){
                System.out.print(num[i]+" ");
            }
            System.out.println();
            return;
        }
        for(int i=1;i<=n;i++){
            num[depth]=arr[i];
            dfs(depth+1,n,m,arr);
        }
    }

}

위의 최종 코드에서는 StringBuilder를 활용해 I/O작업을 최소한으로 처리했지만 해당 코드처럼 재귀안에서 출력처리를 할 경우 

I/O 작업이 많아져 시간초과 발생가능성이 생기며 실제로 해당 코드는 IDE에서는 옳은 출력값이 나오지만 백준에서는 시간초과라는 결과가 나온다.

 

 N과 M 시리즈 

https://hmkang32180116.tistory.com/127

[문제 풀이] 백준 15649번 N과 M(1) JAVA _다시풀이

 

https://hmkang32180116.tistory.com/132

[문제 풀이] 백준 15650번 N과 M(2) JAVA

 

https://hmkang32180116.tistory.com/178

[문제 풀이] 백준 15651번 N과 M(3) JAVA

 

https://hmkang32180116.tistory.com/179

[문제 풀이] 백준 15652번 N과 M (4) JAVA

 

https://hmkang32180116.tistory.com/180

[문제 풀이] 백준 15654번 N과M(5) JAVA

 

https://hmkang32180116.tistory.com/181

[문제 풀이] 백준 15655번 N과M(6) JAVA