백준 15685번 - N과 M(11)

문제

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

리뷰

처음에 이 문제를 접근할 때 이전의 N과 M 시리즈를 풀이했던 경험을 바탕으로
별 생각없이 동일한 논리로 로직을 작성하였었다.

처음 작성한 로직은 문자열 List 형태로 답안들을 저장하고 dfs 로직내에서
M 의 깊이에 도달했을 때 기존 저장된 순서의 역으로 답안들과 비교하여
중복되는 경우가 있으면 답안 List 에 추가하지 않는 방식이었다.

하지만, 해당 로직의 경우 결론적으로 모든 경우를 계산하기에 시간복잡도 조건을
통과하지 못하였고 애초에 중복된 경우를 진입하지 않는 식으로 로직을 수정해야 했다.

로직을 간결하게 구성해야 하는 접근 태도를 다시 상기시키게 해준 문제였다..

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static int N, M;
    static int[] nums;
    static int[] arr;
    static StringBuilder answer = 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 = parseInt(st.nextToken());
        M = parseInt(st.nextToken());

        nums = new int[N];
        arr = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < nums.length; i++)
            nums[i] = parseInt(st.nextToken());

        Arrays.sort(nums);

        dfs(0);

        System.out.print(answer);

        br.close();
    }

    static void dfs(int depth) {
        if (depth == M) {
            for (int val : arr)
                answer.append(val + " ");
            answer.append("\n");
            return;
        }

        int prev = -1;
        for (int val : nums) {
            if (prev != val) {
                prev = val;
                arr[depth] = prev;
                dfs(depth + 1);
            }
        }
    }
}

결과