[알고리즘] 백준 15656 N과 M (7) -백트래킹- 자바

 

 

 

 

https://www.acmicpc.net/problem/15656

15656번: N과 M (7)

 

 

 

오랜만에 알고리즘을 풀고 백트래킹의 기본이라 할 수 있는 N과 M 시리즈를 풀어봤습니다.  

확실히 오랜만에 자바를 사용하고 알고리즘을 풀었더니 없던 실력도 많이 줄은 것 같네요.. ㅠ

 

주어진 숫자를 여러번 사용할 수 있지만 오름차순으로 중복되지 않은 순열을 출력해야 했습니다.

그러므로 isVisited[] 같은 중복을 체크하는 Boolean 형 타입은 필요하지 않고 StringBuilder와 순열을 저장할 배열만을 사용했습니다. 추가로 오름차순으로 출력해야하므로 정렬을 하는 전처리도 진행하였습니다.

 

 

풀이는 다음과 같습니다. 

 

[Java]

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int N;
    private static int M;
    private static int[] nums;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums);
        dfs(0, new int[M]);
        System.out.println(sb.toString());
    }

    private static void dfs(int depth, int[] answers) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(answers[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            answers[depth] = nums[i];
            dfs(depth + 1, answers);
        }
    }
}

 

 

 

https://github.com/mtjin/algorithm_practice/commit/8e764158039d010159aef2bb64e6ed1499e4d802

백준 15656 풀이 · mtjin/algorithm_practice@8e76415

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!