[백준] no15663: N과 M (9) - (중복 미허용/visited 사용한 방법)

문제

* N개의 숫자 중 M개를 구하는 방법
* 단, N개의 숫자 중 중복이 있을 수 있고,
* 같은 차례에 있는 숫자는 중복선택이 불가함

---

원리

1. 백트래킹 (DFS)

2. 재귀

 

---

풀이방법

재귀를 이용한 풀이

* 1. 입력받은 수들을 ArrayList에 담고, 오름차순 정렬
* 2. Combination(재귀 메소드)를 이용해 0번째부터 카운트하며 재귀 시작
* 3. 뽑아야 하는 개수 M이 되기 전까지 재귀를 통한 반복문을 진행
* 4. 중복을 제거하기위해 방문 체크를 시행(visited) -> 방문 후 재귀를 시행
* 5. 방문한 곳에대한 재귀로 해당 경우의 수를 모두 구한 뒤, 다시 방문을 해제하여 다른 경우에서 방문할 수 있도록 허용해줌
* 6. 모든 경우의 수를 구한 뒤, 같은 경우에 대해 중복 제거 실행
* 7. 최종적으로 구해진 모든 경우의 수를 출력

---

나의 코드

1. [실패] 재귀사용 : 중복 선택이 허용된 코드가 되어버림

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N;
    private static int M;
    private static List<Integer> nums = new ArrayList<>();
    private static int[] subset;
    private static List<String> results = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        subset = new int[M];

        StringTokenizer numbers = new StringTokenizer(br.readLine(), " ");
        for(int i =0; i<N ; i++) nums.add(Integer.parseInt(numbers.nextToken()));
//        nums = nums.stream().distinct().sorted().collect(Collectors.toList()); // 중복된 항목을 제거 후 수열을 구하는 방법
        Collections.sort(nums);

        Combination(0, 0);

        results = results.stream().distinct().collect(Collectors.toList());

        bw.close();
    }

    private static void Combination(int cnt, int k) throws IOException {
        if(cnt==M) {
            String str = "";
            for(int i = 0; i<M ; i++) str += subset[i] + " ";
            results.add(str);
            return;
        }

        for(int i=k ; i<N ; i++) {
            subset[cnt] = nums.get(i);
//            Combination(cnt+1, i);
            Combination(cnt+1, k);
        }
    }

 

2. [실패] visited를 이용해 중복을 제거 시도 -> 테스트 코드는 성공, 제출에서 틀림

: 5 3, 1 3 5 7 9 로 실행시 왜 틀렸는지 알 수 있음 (visited 문제)

private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int N;
private static int M;
private static List<Integer> nums = new ArrayList<>();
private static int[] subset;
private static List<String> results = new ArrayList<>();
private static boolean[] visited;

public static void main(String[] args) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    subset = new int[M];
    visited = new boolean[N];

    StringTokenizer numbers = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < N; i++) nums.add(Integer.parseInt(numbers.nextToken()));
    Collections.sort(nums);

    Combination(0, 0);

    results = results.stream().distinct().collect(Collectors.toList());

    for (int i = 0; i < results.size(); i++) bw.write(results.get(i) + "\n");

    bw.close();
}

private static void Combination(int cnt, int k) {
    if (cnt == M) {
        String str = "";
        for (int i = 0; i < M; i++) str += subset[i] + " ";
        results.add(str);

        int visitCnt = 0;
        for(int i=0;i<visited.length; i++) if(visited[i]) visitCnt++;
        if(visitCnt==visited.length) visited = new boolean[N];

        return;
    }

    for (int i = k; i < N; i++) {
        if(!visited[i]) {
            subset[cnt] = nums.get(i);
            visited[i] = true;
            Combination(cnt + 1, k);
        }
    }
}

 

3. [성공] 방문 체크를 위한 위치가 문제였음

: 방문 체크 후 재귀를 돌리고, 재귀가 끝난 다음 다시 방문 해제해주는 원리로 해결

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class no15667 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N;
    private static int M;
    private static List<Integer> nums = new ArrayList<>();
    private static int[] subset;
    private static boolean[] visited;
    private static List<String> results = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        subset = new int[M];
        visited = new boolean[N];

        StringTokenizer numbers = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) nums.add(Integer.parseInt(numbers.nextToken()));
//        nums = nums.stream().distinct().sorted().collect(Collectors.toList()); // 중복된 항목을 제거 후 수열을 구하는 방법
        Collections.sort(nums);

        Combination(0);

        results = results.stream().distinct().collect(Collectors.toList());

        for (int i = 0; i < results.size(); i++) bw.write(results.get(i) + "\n");

        bw.close();
    }

    private static void Combination(int cnt) {
        if (cnt == M) {
            String str = "";
            for (int i = 0; i < M; i++) str += subset[i] + " ";
            results.add(str);
            return;
        }

        for (int i = 0; i < N; i++) {
            if(!visited[i]) {
                subset[cnt] = nums.get(i);
                visited[i] = true; // 방문 체크 후, 재귀를 돌리고
                Combination(cnt + 1); 
                visited[i] = false; // 재귀가 끝나면 해당 부분은 다시 방문 해제 (여기가 포인트)
            }
        }
    }
}

---

Chat GPT 코드

필자의 첫번째 코드와 같이 중복된 코드를 솎아내지 못한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class no15667 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = br.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int m = Integer.parseInt(line1[1]);
        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(nums); // sort the input numbers in ascending order
        List<String> res = generateSequence(nums, m, new ArrayList<>()).stream().distinct().sorted().collect(Collectors.toList());
        for (String seq : res) {
            System.out.println(seq);
        }
    }

    public static List<String> generateSequence(int[] nums, int m, List<Integer> cur) {
        if (cur.size() == m) {
            StringBuilder sb = new StringBuilder();
            for (int num : cur) {
                sb.append(num).append(" ");
            }
            return Arrays.asList(sb.toString().trim());
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            cur.add(nums[i]);
            res.addAll(generateSequence(nums, m, cur)); // recursively generate the sequence
            cur.remove(cur.size() - 1);
        }
        return res;
    }
}