[백준] 16883번: N과 M (9)

💡문제 분석 요약

자연수 N, M을 입력받아, “N개의 자연수 중에서 M개를 고른 수열”을 만족하는 길이가 M인 수열을 모두 출력하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 512MB

 

💡알고리즘 설계

• 입력받은 N개의 수를 정렬한다.
• 백트래킹을 사용해 길이가 M인 모든 가능한 수열을 생성한다.
  • 각 단계에서 사용하지 않은 숫자를 선택한다.
  • 선택한 숫자를 수열에 추가하고, 다음 단계로 넘어간다.
  • 수열의 길이가 m이 되면 결과에 추가한다.
• 생성된 수열들을 LinkedHashSet에 저장해 중복을 제거하고 오름차순을 유지한다.
• 사용한 주요 변수:
  • numbers[]: 입력받은 N개의 수를 저장하고 정렬하는 배열
  • sequence[]: 현재 만들고 있는 수열을 저장하는 배열
  • visited[]: 각 숫자의 방문 여부를 저장하는 배열.
  • LinkedHashSet<String> result: 생성된 모든 수열을 저장.

 

💡코드

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

public class Main {
    static int n, m;
    static int[] sequence, numbers;
    static boolean[] visited;
    static LinkedHashSet<String> result = new LinkedHashSet<>();

    static void backTracking(int depth) {
        if(depth == m) {
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<m; i++) {
                sb.append(sequence[i] + " ");
            }
            result.add(sb.toString());
            return;
        }

        for(int i=0; i<n; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            sequence[depth] = numbers[i];
            backTracking(depth + 1);
            visited[i] = false;
        }
    }

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

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        visited = new boolean[n];
        sequence = new int[n];
        numbers = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(st.nextToken());
            numbers[i] = num;
        }
        Arrays.sort(numbers);

        int depth = 0;
        backTracking(depth);
        for(String i : result) {
            System.out.println(i);
        }
    }
}

 

💡시간복잡도

시간복잡도는 잘 모르겠어서 Claude를 사용해서 답변을 받았다.

O(N * M * N! / (N-M)!)
⇒ N개 중 M개를 선택하는 순열의 수에 각 순열을 생성하는 데 필요한 시간을 곱한 것입니다.

 

💡 틀린 이유

결과의 중복 제거를 위해 HastSet을 사용했지만, HastSet은 오름차순 정렬이 되지 않았다.

HashSet은 삽입 순서를 보장하지 않아서 정렬된 결과를 얻을 수 없다.

중복을 제거하면서도 숫자의 원래 정렬 순서를 유지해주는 LinkedHashSet를 사용해서 해결했다.

 

💡 틀린 부분 수정

HashSet을 LinkedHashSet으로 변경하여 해결했다.

 

💡 느낀점 or 기억할정보

백트래킹을 개념 정리하면서 어느 정도 이해를 했다고 생각했는데, 막상 문제로 풀어보니 어려운 것 같다.ㅠ 여러 레퍼런스를 찾아보며 백트래킹에 대해 더 알아봐야할 것 같다.

HashSet과 LinkedHashSet의 차이점을 기억해두고, 다른 문제에서도 적절하게 사용하면 좋을 것 같다. 중복 제거와 순서 유지가 모두 필요할 경우 LinkedHashSet 이용하기!