더 이상 물러설 곳이 없다

www.acmicpc.net/problem/15652

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

단, 내림차순이 아닌 수열들만 출력한다.

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

codeung.tistory.com/54

N과 M (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 boolean isNotDesc(int len) {
        for (int i = 0; i < len; i++) {
            if (permu[i] > permu[i + 1]) {
                return false;
            }
        }
        return true;
    }

    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;
            if (isNotDesc(deptNow)) {
                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();
    }
}

N과 M (3) 코드에서 isNotDesc() 하나만 추가되었다.

dfs를 재귀하기 전 검사를 통해 조건에 맞지 않는 수열로의 재귀를 막았다.

www.acmicpc.net/problem/15651

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

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

codeung.tistory.com/52

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

풀이 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를 쓰자

www.acmicpc.net/problem/15650

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

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

단, 오름차순이 유지되는 수열만 출력한다.

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static boolean[] check = null;

    public static boolean isAsc(String comb) {
        for(int i = 0; i < comb.length() - 1; i++) {
            if(comb.charAt(i) > comb.charAt(i + 1)) {
                return false;
            }
        }
        return true;
    }

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

        for(int i = 0; i < numbers.length(); i++) {
            if(check[i] == false) {
                String temp = comb;
                comb += numbers.charAt(i);
                check[i] = true;

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

                // 백트래킹
                check[i] = false;
                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());
        check = new boolean[n];

        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);

            check[i] = true;
            dfs(m, 1, comb, numbers);

            // 백트래킹
            check[i] = false;
        }
    }
}

codeung.tistory.com/52

이 문제에서 오름차순 수열만 출력한다는 조건만 추가된 문제.

isAsc() 를 통해 순열이 완성된 후 오름차순 여부만 추가로 체크해주었다.

이전 문제에서는 출력하기 전에 아예 comb를 갱신할 때부터 공백을 같이 넣어주었는데, 이 공백 때문에 isAsc() 가 제대로 동작하지 않았다.

공백을 출력부에서 처리하도록 바꿔주어 정답 처리 되었다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

isAsc 사용하지 말고 그냥 !check[i] 검사할 때 오름차순 검사까지 같이 해서 오름차순인것만 재귀하면 되잖아!

www.acmicpc.net/problem/15649

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

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

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static boolean[] check = 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++) {
            if(check[i] == false) {
                String temp = comb;
                comb += numbers.charAt(i) + " ";  // 출력 주의. 숫자 사이에 공백 넣어야 함
                check[i] = true;

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

                // 백트래킹
                check[i] = false;
                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());
        check = new boolean[n];

        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) + " ";

            check[i] = true;
            dfs(m, 1, comb, numbers);

            // 백트래킹
            check[i] = false;
        }
    }
}

프로그래머스만 풀다가 백준을 풀려니 입출력이 매우 거슬렸다.

문제는 전형적인 백트래킹 문제이다.

숫자들을 한자리씩 사용하기 쉽도록 String 형태로 넘겨줬다.

처음엔 완성된 수열들을 배열에 담아서 정렬을 해야겠다고 생각했는데 생각해보니 어차피 순서대로 만들어지기 때문에 굳이 정렬할 필요도 없었고, 배열에 담을 필요 없이 완성되는 순간 바로 출력하도록 했다.