[문제 풀이] 백준 15657번 N과 M (8) JAVA

문제

  문제접근 방법   

해당 문제는 N개의 자연수와 자연수 M이 주어졌을 때, 문제에서 제시하는 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하는 문제이다. 본 문제는 N과 M(4) 번 문제와 굉장히 유사한 풀이를 가진 것을 알 수 있었다.

여기 핵심은 선택된 수열이 각각 비내림차순이어야한다는 점이었다.

 

 

< 초기 코드  1 >

import java.util.*;

public class Main{
    public static StringBuilder sb=new StringBuilder();
    public static int num[];
    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];
            
            if(depth!=0){
                if(num[depth-1]<=arr[i]){dfs(depth+1,n,m,arr);}
            }
            else{
                dfs(depth+1,n,m,arr);
            }
            
        }
    }
}

해당 문제는 앞서 풀었던 N과M 문제들처럼 별도의 방문처리를 하지 않지만 StringBuilder를 활용하지 않고 바로 출력해도 수열이 비내림차순 이어야 한다는 조건이 존재해서 I/O 작업이 줄어 시간초과가 발생하지 않는다.

< 초기 코드  2 >

import java.util.*;

public class Main{
    public static StringBuilder sb=new StringBuilder();
    public static int num[];
    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++){
                System.out.print(num[i]+" ");
            }System.out.println();
            return;
        }
        for(int i=1;i<=n;i++){
            num[depth]=arr[i];
            
            if(depth!=0){
                if(num[depth-1]<=arr[i]){dfs(depth+1,n,m,arr);}
            }
            else{
                dfs(depth+1,n,m,arr);
            }
            
        }
    }
}

위에서 언급하였듯이 본 문제에서는 별도의 방문처리는 없지만 선택된 수의 수열이 비내림차순이어야한다는 조건이 존재해 위처럼 코드를 작성하여도 I/O 작업이 최대치에 도달하지는 않아 시간초과는 발생하지 않는다. 다만 최대치에 가까운 면 I/O 병목 현상이 발생할 가능성도 존재하고 I/O 호출 횟수 최소화는 속도 향상으로 이어지기 때문에 StrinBuilder를 활용하면 더 좋은 코드를 완성할 수 있다. 

< 최종 코드 >

import java.util.*;

public class Main{
    public static StringBuilder sb=new StringBuilder();
    public static int num[];
    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,1,n,m,arr);
        System.out.println(sb);
    }
    public static void dfs(int depth,int start,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=start;i<=n;i++){
            num[depth]=arr[i];
            dfs(depth+1,i,n,m,arr);
        }
    }
}

최종적으로 위에서는 조건문으로 나누어서 비내림차순을 처리했지만 start 값을 매개변수로 넘기고 start에 i를 계속 넘겨준다면 위와 같이 해결할 수 있다. 예를 들어 start=1일때 계속 반복하다가 2가 되었을대 인덱스 값이 2 아래로는 절대로 안 내려가기 때문에 이미 오름차순으로 정리된 arr에서 비내림차순으로 선택할 수 있다는 게 보장된다.

 

 참고 자료 

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

 

https://hmkang32180116.tistory.com/182

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