관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DFS, BFS, 시뮬, 백트래킹

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

막무가내막내 2021. 11. 22. 23:23
728x90

 

 

 

 

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

 

15656번: N과 M (7)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

 

 

 

오랜만에 알고리즘을 풀고 백트래킹의 기본이라 할 수 있는 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

 

github.com

 

 

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

 

 

 

728x90
Comments