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

문제

  문제접근 방법   

본 문제는 1부터 N까지 자연수 중에서 M개를 고른 수열(같은 수를 여러 번 골라도 된다.)을 출력하는 프로그램을 작성하는 문제로

처음 문제를 읽고 방문처리 없이 구현하면 해결이 가능하다고 생각해 아래와 같이코드를 작성하였다. 

< 초기 코드  >

import java.util.*;

public class Main{
    public static int num[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        num=new int[m];
        dfs(0,n,m);
    }
    public static void dfs(int depth,int n,int m){
        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]=i;
            dfs(depth+1,n,m);
        }
    }
}

처음에는 단지 방문처리 없이 문제를 해결하는 문제인가보다라고 생각하고 위와 같이 풀이했었다.

하지만 시간초과라는 결과를 받았고 무엇이 문제인지 고민해본 결과 방문처리가 없어 모든 재귀를 다 접근하는데

이때마다 Sytem.out.print를 호출해 I/O 작업이 발생하게 되어 시간초과가 난다는 결론이었다. 

예를 들어 n=7 m=7일때 나올수 있는 경우의 수는 7의 7승 823,543인데

이럴 경우 위의 코드처럼 결과 값이 있을때마다 I/O 작업이 발생되면 출력시간이 많이 걸리게 되어 시간초과가 나오는 것이다.

< 최종 코드 >

import java.util.*;

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

위처럼 StringBuilder를 활용해 출력값을 한곳에 저장했다가 출력하는 방식으로 문제를 해결하였다.

다만 StringBuilder에 매몰된 나머지 StringBuilder을 2번 선언해서 사용하였는데 

초기 코드에 dfs 함수의 if문안의 for문에서 출력대신 StringBuilder을 사용하는것으로도 해결이 가능하다.

 

  마무리  

본 문제는 문제를 해결할때 단순히 시간복잡도 뿐만 아니라 입출력의 횟수등 여러 부분을 고려하고 계산해 문제를 접근해야한다는 것을 알려주는 좋은 문제였다. n과 m(1)에서는 StringBuilder를 활용하지 않아도 시간초과가 나지 않았었는데 이때는 

입출력 호출횟수가 약 4만회 정도로 안전했지만 본 문제에서 같은 수를 허용하면서 호출횟수가 80만회가 넘어 시간초과를 유발한것을 알수 있었다. 

중요한 것은 자바에서는 출력횟수가 10만을 넘어가게 되면 1초안에 해결이 힘들다는 것을 인지하고 문제를 접근해야한다는 것이다.

 

 참고 자료 

- StringBuilder 활용 정리

 

 N과 M  시리즈 

https://hmkang32180116.tistory.com/127

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

https://hmkang32180116.tistory.com/132

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