[BOJ] 15651 - N과 M (3) JAVA

www.acmicpc.net/problem/15651

15651번: N과 M (3)

1~N 의 자연수를 사용 하여 나타낼 수 있는 M자리 수열을 모두 출력해야한다. (숫자들의 중복 사용 허용)

수열들의 순서는 사전 순 오름차순으로 한다.

 

 

codeung.tistory.com/52

[BJ] N과 M (1) JAVA

이 문제에서 중복 허용으로 조건만 바꾼 문제.

 

 

 

풀이 1. (시간 초과)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;

    // 한자리씩 사용하기 쉽도록 comb, numbers는 String으로 나타냈다
    public static void dfs(int dept, int deptNow, String comb, String numbers) {
        if (dept == deptNow) {
            System.out.println(comb);
            return;
        }

        for (int i = 0; i < numbers.length(); i++) {
            String temp = comb;
            comb += numbers.charAt(i) + " ";  // 출력 주의. 숫자 사이에 공백 넣어야 함

            dfs(dept, deptNow + 1, comb, numbers);

            // 백트래킹
            comb = temp;
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String numbers = "";
        for (int i = 1; i <= n; i++) {
            numbers += String.valueOf(i);
        }

        for (int i = 0; i < n; i++) {
            char ch = numbers.charAt(i);
            String comb = String.valueOf(ch) + " ";
            dfs(m, 1, comb, numbers);
        }
    }
}

 

N과 M (1) 의 정답에서 check의 역할만 없애주었는데 시간 초과가 발생했다.

 

이전 코드의 문제점

 

1. 쓸데없이 String numbers를 사용했다. 

어차피 1~N의 "연속된" 숫자들을 사용하는 것이기 때문에 반복문의 i 로도 충분히 표현이 가능한데 굳이 String을 넘겨주도록 해서 부하를 증가시켰다.

 

2. System.out.println() 

테스트 케이스의 덩치가 꽤 컸는지 println을 사용하면 시간 초과가 발생했다. 

이러한 문제를 처음부터 피해버리기 위해 Scanner, println() 의 사용을 애초에 사용하지 않고 br, bw, sb의 사용을 생활화해야겠다.

 

 

 

풀이 2. (시간 초과)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;

    public static void dfs(int dept, int deptNow, StringBuilder comb, String numbers) {
        if (dept == deptNow) {
            System.out.println(comb);
            return;
        }

        for (int i = 0; i < numbers.length(); i++) {
            comb.append(numbers.charAt(i));
            comb.append(" ");

            dfs(dept, deptNow + 1, comb, numbers);

            // 백트래킹
            comb.deleteCharAt(comb.length() - 1);  // 공백 제거
            comb.deleteCharAt(comb.length() - 1);  // 숫자 제거
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String numbers = "";
        for (int i = 1; i <= n; i++) {
            numbers += String.valueOf(i);
        }

        for (int i = 0; i < n; i++) {
            sb.append(numbers.charAt(i));
            sb.append(" ");

            dfs(m, 1, sb, numbers);

            // 백트래킹
            sb.deleteCharAt(sb.length() - 1);  // 공백 제거
            sb.deleteCharAt(sb.length() - 1);  // 숫자 제거
        }
    }
}

 

sb를 사용하긴 했지만 여전히 시간초과가 발생했다.

 

코드의 문제점 

1. sb라고 만사형통은 아니다?

내 추측이지만 sb를 사용한 출력도 많이 사용하면 시간 소요가 큰 것 같았다.

 

 

 

풀이 3. (정답)

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static int[] permu = null;
    static int n, m;

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for(int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 1; i <= n; i++) {
            permu[deptNow] = i;
            dfs(dept, deptNow + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            permu[0] = i;
            dfs(m, 1);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

sb 출력을 한 번만 해도 되는 식으로 고쳤다.

 

이전 코드는 dfs의 재귀를 이어나가며 sb.append() 를 하고 수열이 완성됐을 때마다 sb 출력을 실행했다.

바뀐 코드는 수열이 완성됐을 때 한꺼번에 sb.append() 하고 모든 dfs가 완료된 후에 sb 출력을 한 번만 실행한다.

 

 

 

 

배운 점

 

1. 백준에서 StringBuilder를 사용해 출력할 때 개행문자를 sb에 넣음으로써 모든 출력을 한 번의 출력만으로 완료할 수 있다.

 

2. Scanner, println을 멀리하자. 그냥 처음부터 br, bw, sb를 쓰자