백준 15663번 : N과 M (9) [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

N과 M (9) 실버 2

 

📖 문제

 

N과 M 9번째 시리즈

N개의 자연수 중 M개를 고른 수열이면서 그 수열이 중복되면 안된다. 

 

입력받은 N개의 자연수를 우선 오름차순으로 정렬한 후 

백트래킹 탐색을 한다. 

수열을 문자열로 만들고 

Set에 중복 체크를 한 다음 없다면

Queue에 넣어서 저장

 

탐색이 끝나면

 

Queue를 다 꺼내서 출력하면 된다. 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    static Set<String> set = new HashSet<>(); // 수열 중복 체크
    static StringBuilder sb = new StringBuilder(); // 수열 만들기용
    static List<Integer> list = new ArrayList<>(); // m개 뽑은 수를 저장
    static Queue<String> q = new LinkedList<>(); // 답을 저장
    static boolean[] visited;
    static int[] seq;
    static int n;
    static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visited = new boolean[n];
        seq = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(seq);
        backtracking();

        while (!q.isEmpty()) {
            sb.append(q.poll()).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }



    private static void backtracking() {

        // 길이가 m이 됐다면
        if (list.size() == m) {

            // 수열 만들기
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i)).append(" ");
            }

            // 중복체크
            if (!set.contains(sb.toString())) {
                set.add(sb.toString());
                q.add(sb.toString());
            }
            sb.delete(0, sb.length()); // 임시로 만든 수열 지우기
            return;
        }

        //백트래킹
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            list.add(seq[i]);
            visited[i] = true;
            backtracking();
            list.remove(list.size() - 1);
            visited[i] = false;

        }
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.