[백준/BOJ] 15664번 N과 M (10) (자바/Java)

 

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

15664번: N과 M (10)

---

1. 문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

2. 풀이

우선 기존에 풀었던 백트래킹 문제는 메서드의 인자가 너무 많았다.

2023.07.18 - [BOJ/BackTracking] - [백준/BOJ] 2992번 크면서 작은 수 (자바/Java)

 

그래서 static 필드로 옮겨준 후, 진행했다. 이 문제에 대해 글을 쓰는 이유는 기존에 내가 사고했던 방식보다 너무 깔끔하고 간단하지만 완벽한 코드이기에 소개하고 싶었다.

 

이 문제에서는 중복된 수열의 값이 입력될 수 있다. 하지만 출력에서 중복된 수열이 나오면 안 된다. 그렇다고 입력될 때 중복되는 값을 입력된 경우를 무시해준다고 하면,  예제 3번과 같은 결과를 도출할 수 없다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int M;
    static int N;
    static int[] input;
    static boolean[] visited;
    static int[] res;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        input = new int[N];
        visited = new boolean[N];
        res = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) input[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(input);

        BackTracking(0, 0);

        System.out.println(sb);
    }

    private static void BackTracking(int x, int start) {
        if(x==M){
            for(int i : res) sb.append(i+" ");
            sb.append("\n");
            return;
        }

        int tmp = 0; // 출력되는 수열이 겹치지 않게 판단해주는 변수
        for(int i=start; i<N; i++){
            if(!visited[i] && tmp != input[i]){ // tmp == input[i]이면 중복된 수열이 나온다.
                visited[i] = true;
                res[x] = input[i];
                tmp = input[i];
                BackTracking(x+1, i+1);
                visited[i] = false;
            }
        }
    }
}

 

이 코드에서 BackTracking 메서드 내 for문 전에 선언된 tmp 변수가 핵심이다. 여기서 tmp == input[i]가 된다면 tmp 변수가 이전에 Input[i] 로 선언되었었다는 뜻이다. 따라서 우리가 tmp == input[i]일 때도, 수열을 만들어서 넣어주게 되면, 중복된 수열이 나오게 된다.

 

즉, tmp == input[i]일 때를 다루지 않으면, 중복된 수열은 나오지 않으면서 우리가 원하는 결과를 얻을 수 있다. 재귀적 사고로 코드를 잘 살펴보길 바란다.

 

 

3. 결과

 

4. 총평

 - 백트래킹을 이해하기 위해서는 재귀적 사고가 필수로 요해졌다. 우리가 기본적으로 자연스레 갖고있는 절차적 사고에서 탈피해 재귀적 사고를 하는 것은 쉬운 일이 아니었다. 그렇기에, 나는 백트래킹 문제를 풀 때도 이러한 방식으로 풀지 못했던 것 같다. 한 문제에 여러가지 풀이가 존재하기에 재귀적 사고를 이용하지 않아도 풀 수는 있다. 하지만 난이도가 올라가면서, 어려운 문제들을 해결하기 위해서라면 이러한 사고 능력을 꼭 갖추어야한다.