[BOJ] 15650 - N과 M (2) JAVA

www.acmicpc.net/problem/15650

15650번: N과 M (2)

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

[BJ] N과 M (1) JAVA

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

 

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

 

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

 

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

 

 

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

 

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