백준 15665번 N과 M (11)

오늘은 오랜만에 백트래킹 문제를 풀어보았다. 백준에서 백트래킹으로 가장 기본적인 문제 시리즈인 N과 M의 11번째 문제를 풀어보았다. 오랜만에 백트래킹을 풀어서인지 실버 문제였는데도 조금 오래 걸렸다.

🔥 문제

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

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

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

출력

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

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

문제 풀이

테스트 케이스를 보니 주어진 N개의 수 중에서 중복된 값이 주어지는 경우가 있어서 이 부분에 대해서 처음부터 중복 제거를 하고 가는 것이 이후 로직을 짜는데 편하겠다 싶어서 ArrayList를 생성하여 숫자들을 담으면서 중복을 제거해주었다. 그리고 사전 순으로 출력하라고 하였으니 미리 중복 제거한 숫자들을 오름차순 정렬을 해주었다. 그 후 M의 길이만큼 백트래킹을 진행해주니 올바른 답이 도출될 수 있었다. 여기서 주의할 점은 같은 수를 여러 번 골라도 된다고 하였으므로 방문처리는 따로 해주지 않았다.

그런데 처음에는 출력 부분을 StringBuilder로 출력하지 않고 System.out.print()로 출력을 하니 시간초과가 발생하였다. 그래서 어떤 부분이 문제인지 잘 몰랐었는데 파타곤이야 형(알고리즘 고수라서 많이 배우고 있는 형이다 ㅎㅎ)이 출력 부분에서 시간초과가 발생했을테니 StringBuilder로 출력해보라고 해서 시도했는데 놀랍게도 통과가 되었다. 이 부분에 대해서 원인을 알기 위해서 GPT한테 물어보니 System.out.print()를 많이 호출하게 되면 입출력 병목이 발생하게 되어 시간 초과가 발생할 수 있다고 하였다. 앞으로는 이 부분을 잘 인지하여 알고리즘 문제를 풀어야겠다....

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;


class Main {
    static int N;
    static int M;

    static ArrayList<Integer> arr = new ArrayList<>();
    static int[] visited;

    static StringBuilder result = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer info = new StringTokenizer(br.readLine());

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

        // 숫자들을 담으면서 중복 제거하기
        StringTokenizer nums = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(nums.nextToken());

            if (!arr.contains(num)) {
                arr.add(num);
            }
        }

        // 정렬하기 - 오름차순
        Collections.sort(arr);
        
        // 방문 리스트 생성
        visited = new int[M];

        // 담은 후 dfs로 길이만큼 조합하기 - 길이는 M만큼이다.
        dfs(0);

        System.out.println(result.toString());
    }

    private static void dfs(int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                result.append(visited[i]).append(" ");
            }
            result.append("\n");
            return;
        }

        for (int i = 0; i < arr.size(); i++) {
            visited[depth] = arr.get(i);
            dfs(depth + 1);
        }
    }

}

파타곤이야 블로그 주소 https://velog.io/@yg9618/posts