박시은

(❁´◡`❁)

15 분 소요


문제집 N과 M


N과 M 시리즈는 백트래킹을 공부하기 아주 좋은 문제들이다.
총 12문제로 구성되어 있으며 아래와 같이 목차에 부제목을 달아봤다.

// 기초 백트래킹 (1~4번)
1. N과 M (1) - 순열
2. N과 M (2) - 조합
3. N과 M (3) - 중복 순열
4. N과 M (4) - 중복 조합

// 입력 수열 기반 확장 문제 (5~8번)
5. N과 M (5) - 입력 수열로 만드는 중복 없는 순열
6. N과 M (6) - 입력 수열 조합
7. N과 M (7) - 입력 수열 중복 순열
8. N과 M (8) - 입력 수열 중복 조합

// 중복 제거 응용 문제 (9~12번)
9. N과 M (9) - 입력 수열 중복 없는 순열 (중복 제거)
10. N과 M (10) - 입력 수열 조합 (중복 제거)
11. N과 M (11) - 입력 수열 중복 순열 (중복 제거 없음)
12. N과 M (12) - 입력 수열 중복 조합 (중복 제거)

1번부터 4번까지는 백트래킹의 기초를 다지기 위한 문제들이고, 9번부터 12번까지는 이를 응용하여 다양한 조건을 추가한 확장 문제들이다.

이번 글에서는 이 8문제를 집중적으로 정리해보려 한다.


🧠 선행 지식

백트래킹이란?

현재 상태에서 가능한 모든 선택지를 따라가며 정답을 찾는 탐색 방법

  • 완전탐색의 일종
  • 모든 후보를 고려하되, 불필요한 탐색은 가지치기(Pruning) 로 줄인다
  • 모든 경우의 수를 고려해야 할 때 사용
  • 예시
    • 미연시 게임: 모든 루트(선택지)를 탐색
    • 오목: 가능한 모든 수를 놓아보며 승리 여부 판단


백트래킹 구현 방식

  • 빈 리스트에서 시작해서, 가능한 수를 하나씩 추가해 나간다.
  • 이미 사용한 수는 제외한다.
  • 조건을 만족하지 않으면 되돌아가며(Backtrack) 다른 선택지를 탐색한다.

즉, 상태를 넘나드는 방식으로 탐색하는 방식이다.


[참고] 상태공간 트리란?

문제를 풀기 위한 모든 경우의 수(상태)를 트리 형태로 나타낸 구조

  • 루트: [] (초기 상태)
  • 자식 노드: 어떤 수를 선택한 이후의 상태
  • 리프 노드: 원하는 길이(M)를 만족하는 상태


백트래킹 문제 접근법

백트래킹 문제를 풀기 전, 아래 3단계만 파악하면 전략이 바로 보인다.

  • 조합 vs 순열
  • 중복 허용 여부 확인 (중복 순열 / 중복 조합)
  • 오름차순 조건 여부 파악 (비내림차순인지 아닌지)
조건 설명 구현 방식
중복 허용 X 같은 수 한 번만 사용 visited[i] = true 사용
중복 허용 O 같은 수 여러 번 사용 가능 visited 안 씀
오름차순 조건 O 수열이 앞 ≤ 뒤 형태 for (int i = start; i < ...) 사용
오름차순 조건 X 아무 순서나 허용 for (int i = 0; i < ...) 사용
순열 순서 중요 매 단계마다 모든 수 탐색
조합 순서 상관 없음 이전보다 큰 수만 탐색 (start 사용)

지금은 이해가 안 될수도 있으니 문제를 풀면서 알아보도록 하자.


오름차순 vs 비오름차순 수열 비교

  • 오름차순 o
    • 앞 원소 ≤ 뒷 원소이면 오름차순이다.
    • 이때, 이전보다 크거나 같은 수만 선택하도록 start 인덱스를 넘겨준다.
    • 구현은 for (int i = start; i < n; i++) 와 같이 한다.
    • 이렇게 하면 현재 위치 이후 값만 고르므로 자연스럽게 오름차순이 유지된다.

      1 1
1 2
1 3
2 4
3 3
4 4


  • 오름차순 x
    • 앞 원소가 뒷 원소보다 클 수 있으므로 오름차순 조건이 없다.
    • 따라서 start 인덱스를 사용하지 않고, for (int i = 0; i < n; i++)를 사용한다.
    • 이 경우 모든 숫자를 매번 다시 탐색하게 된다.

      2 1
3 2
4 3



📌 문제

1. N과 M (1) - 순열

📘 문제 설명

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


📕 문제 해석

이 문제는 순서가 중요한 순열(permutation) 을 구하는 문제이다.

  • 중복 허용 X:
    • 같은 숫자를 두 번 고를 수 없으므로 visited[] 배열을 사용한다.
  • 오름차순 조건 X
    • 수열이 오름차순일 필요는 없으므로, start 매개변수는 필요 없다.
    • 대신 단순히 i = 0부터 순회하면서 가능한 수를 모두 시도하면 된다.
  • 순열
    • 순서가 중요하므로 모든 숫자 위치에 대해 모든 경우를 시도한다.
    • for (int i = 0; i < n; i++)와 같은 전체 탐색이 필요하다.


📙 예시 (N=4, M=2)

예를 들어, N=4, M=2일 때 가능한 수열은 다음과 같다.

  • 입력

    4 2
  • 출력

    1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3


아래의 예시처럼 백트래킹은 상태(State) 를 하나하나 바꿔가며 탐색해나간다.

  • 초기 상태: []
  • 1 선택 -> [1]
  • 다음 수로 2 선택 -> [1, 2] → 출력 -> 되돌아가기
  • 다음 수로 3 선택 -> [1, 3] → 출력 -> 되돌아가기
  • 1 사용했으니 패스 -> 되돌아가기 -> 2 선택 → [2]…


즉, [] → [1] → [1, 3] 이런 식으로
현재 상태에서 가능한 값을 추가하며 다음 상태로 이동한다.

그리고 조건을 만족하지 않거나, 탐색을 마친 경우에는
그 값을 되돌리고(백트래킹), 다시 이전 상태로 돌아간다.

백트래킹은 이렇게 상태의 변화와 복귀를 반복하며 가능한 해를 찾는 모두 탐색한다.


🔍 문제 풀이

dfs를 통해 백트래킹을 구현한다

  1. 1부터 N까지 숫자 중에서 아직 사용하지 않은 숫자를 하나를 선택한다.
  2. 사용한 숫자는 visited[i] = true로 체크하고, 현재 수열 위치인 arr[depth]에 저장한다.
  3. 숫자를 하나 선택할 때마다 depth + 1 을 인자로 전달하여 DFS를 재귀 호출한다.
    • depth는 지금까지 몇 개의 숫자를 골랐는지를 나타내는 재귀의 “깊이”이다.
  4. depth == m이 되면, 수열이 완성된 것이므로 arr 배열을 출력한다.
  5. 이후 visited[i] = false로 백트래킹하여 다음 숫자 조합을 탐색한다.

상태공간트리


👩‍💻 전체 코드

  • DFS 재귀가 완전히 끝나기 전까지는 visited가 해제되지 않는다.
  • visited[i] = true로 어떤 노드를 방문한 상태는, 그 노드에 대한 DFS 재귀가 끝날 때까지 유지된다.
  • 즉, 재귀가 끝난 뒤에야 visited[i] = false로 백트래킹 한다.
import java.io.*;
import java.util.*;

public class Main {
    static int[] arr;  // 수열을 저장할 배열
    static boolean[] visited; // 숫자 사용 여부 체크 배열

    static void dfs(int n, int m, int depth){
        // depth는 현재 수열의 길이(몇 개 선택했는지)
        // m개를 모두 선택했으면 수열 출력
        if (depth == m) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] == false) { // 아직 사용하지 않은 숫자인 경우만 실행

                visited[i] = true; // 숫자 사용 체크

                arr[depth] = i + 1; // 현재위치(depth)에 숫자 저장
                dfs(n, m, depth + 1); // 다음 단계로 이동 (재귀)

                visited[i] = false; // 돌아와서 숫자 사용 해제 (백트래킹)
            }
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[m];
        visited = new boolean[n];

        dfs(n, m, 0); // depth = 0부터
    }
}


2. N과 M (2) - 조합

📘 문제 설명

  • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.


📕 문제 해석

이 문제는 순서가 중요하지 않은 조합(combination) 문제이다.

  • 중복 허용 X
    • 같은 수를 두 번 고르면 안 되므로 i + 1부터 탐색하여 중복 제거
    • 즉, 1 2와 2 1은 같은 것으로 보기 때문에 한 번만 출력해야 한다.
    • visited[] 없이도 start만으로 충분히 처리 가능 -> 백트래킹 구조 자체로 오름차순 필터링 가능하기 때문
  • 오름차순 조건 O
    • 현재 수보다 같거나 큰 수만 선택하도록 start 인덱스를 넘겨준다.
    • for (int i = start; i <= n; i++) 형식으로 구현
  • 조합
    • 순서가 중요하지 않으므로, 앞에 선택한 수보다 크거나 같은 수만 선택


📙 예시 (N=4, M=2)

예를 들어, N=4, M=2일 때 가능한 수열은 다음과 같다.

  • 입력

    4 2
  • 출력

    1 2
1 3
1 4
2 3
2 4
3 4

2 1, 3 1 등은 아예 시도하지 않는다 -> 백트래킹 구조 자체로 오름차순 필터링이 된다!


👩‍💻 전체 코드

순열과 구조는 비슷하지만, start 변수를 넘기면서 오름차순 조합을 생성하는 것이 차이점이다.

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

public class Main {
    static int[] arr;
    static int n, m;

    static void dfs(int start, int depth){
        if(depth == m){
            for(int val : arr){
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }

        for(int i = start; i <= n; i++){
            arr[depth] = i; // 현재 수를 수열에 넣기
            dfs(i + 1, depth + 1); // 다음 수는 i보다 큰 수부터 탐색 (오름차순 보장)
        }
    }

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];
        dfs(1, 0); // 1부터 시작
    }
}


3. N과 M (3) - 중복 순열

📘 문제 설명

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

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


📕 문제 해석

이 문제는 중복을 허용하여 M개를 고른 순열 (중복 순열) 을 구하는 문제이다.

  • 중복 허용 O
    • 같은 수를 여러 번 골라도 되므로 visited[]를 사용하지 않는다.
  • 오름차순 조건 X
    • 수열이 오름차순일 필요가 없으므로 start 매개변수는 필요 없다.
    • for (int i = 1; i <= n; i++)로 모든 수를 탐색한다.
  • 순열
    • 순서가 중요하므로 모든 위치에 대해 모든 수를 사용할 수 있다.


📙 예시 (N=4, M=2)

예를 들어, N=4, M=2일 때 가능한 수열은 다음과 같다. (4*4 = 16개)

  • 입력

    4 2
  • 출력

    1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4


👩‍💻 전체 코드

⚠️ System.out.println을 사용하면 시간초과가 나기 때문에, StringBuilder을 사용해서 풀어야한다.

(앞으로 StringBuilder를 활용해서 풀도록 하겠다-!)

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

public class Main {
    static int n, m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

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

        }

        for(int i=0; i<n; i++){
            arr[depth] = i+1;
            dfs(depth+1);
        }
    }

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

        n = Integer.parseInt(st.nextToken()); // visited 크기
        m = Integer.parseInt(st.nextToken()); // arr 크기

        arr = new int[m];

        dfs(0);
        System.out.println(sb);
    }
}


4. N과 M (4) - 중복 조합

📘 문제 설명

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

  • 1부터 N까지 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.


📕 문제 해석

이 문제는 중복을 허용하여 M개를 고른 조합 (중복 조합) 을 구하는 문제이다.

  • 중복 허용 O
    • 같은 수를 여러 번 골라도 되므로 visited[]를 사용하지 않는다.
  • 오름차순 조건 O
    • 비내림차순(앞 ≤ 뒤)을 만족해야 하므로 start 인덱스를 넘겨준다.
    • for (int i = start; i <= n; i++)로 현재 수 이상부터 탐색한다.
  • 조합
    • 순서가 중요하지 않으며, 이전보다 크거나 같은 수만 선택한다.


📙 예시 (N=4, M=2)

예를 들어, 아래와 같은 입력이 들어왔을 때 수열은 다음과 같다.

  • 입력

    4 2
  • 출력

    1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4


👩‍💻 전체 코드

  • 중복 허용이기 때문에 i를 그대로 넘겨도 된다.
  • 현재 숫자(i)를 포함한 나머지 조합을 계속 탐색하는 구조이다.
import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    static void dfs(int start, int depth){
        if(depth == m){
            for(int val:arr){
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;

        }

        for(int i=start; i<=n; i++){
            arr[depth] = i;
            dfs(i, depth+1); // 중복 허용 → i 그대로 넘김

        }

    }

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

        n = Integer.parseInt(st.nextToken()); // visited 크기
        m = Integer.parseInt(st.nextToken()); // arr 크기

        arr = new int[m];

        dfs(1, 0);
        System.out.println(sb);
    }
}



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

public class Main {
    static int n, m;
    static int[] arr;
    static boolean[] visited;
    static int[] nums;

    static StringBuilder sb = new StringBuilder();

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

        }

        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                arr[depth] = nums[i]; // 입력된 숫자 넣어주기
                dfs(depth+1);
                visited[i] = false;
            }
        }
    }

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

        n = Integer.parseInt(st.nextToken()); // visited 크기
        m = Integer.parseInt(st.nextToken()); // arr 크기
        nums = new int[n];

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

        arr = new int[m];
        visited = new boolean[n];

        Arrays.sort(nums); // 정렬

        dfs(0);
        System.out.println(sb);
    }
}


9. N과 M (9) - 입력 수열 중복 없는 순열 (중복 제거)

📘 문제 설명

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

  • N개의 자연수 중에서 M개를 고른 수열


📕 문제 해석

이 문제는 입력으로 주어진 수열에서 중복 없이 M개를 고른 순열 을 구하는 문제이다.

  • 중복 허용 X
    • 같은 숫자를 두 번 고르면 안 되므로 visited[] 배열을 사용한다.
  • 오름차순 조건 X
    • 수열이 오름차순일 필요가 없으므로 start 매개변수는 필요 없다.
    • 사전 순 출력을 위해 Arrays.sort(nums)를 먼저 해줘야한다.
  • 입력 수열 사용
    • nums[] 배열에 주어진 수열을 저장한 뒤, 정렬하여 탐색한다.
  • 중복 제거
    • 입력 수열에 중복된 숫자가 있을 수 있으므로, LinkedHashSet으로 결과 중복을 제거하였다.


헷갈린점

  • ⚠️ 무조건 LinkedHashSet을 써야한다.
  • 순서를 그대로 유지하면서 중복 제거하려면 LinkedHashSet이 적합하기 때문이다.
    • LinkedHashSet:
      • 입력한 순서 유지
      • Arrays.sort()로 만든 사전 순 그대로 출력됨
      • 수열이 숫자 오름차순처럼 보이게 하려면 LinkedHashSet을 사용하자
    • TreeSet:
      • 자동 오름차순 정렬 (기본은 String 기준)
      • 숫자 “135”, “16” -> 출력: “135”, “16” -> (사전 순 깨짐)
      • 즉, “1” vs “1” → 다음 “3” vs “6” → “3”이 작으므로 “135”가 앞에 옴

참고 블로그 - 그냥 그냥 블로그


  • 정렬 2번 하는 이유
    • 입력 수 정렬 (Arrays.sort(nums)) -> 사전 순으로 탐색이 되도록 하기 위해 필요
    • 출력 순서 유지 (LinkedHashSet) -> 중복 수열 제거 + 삽입 순서대로 출력


  • StringBuilder는 Set<String>에 직접 넣을 수 없다
    • 출력만 할 거면 System.out.println(sb) 해도 상관없지만,
    • Set<String>에 넣으려면 반드시 .toString()으로 문자열로 변환해야 한다.
    • sb는 StringBuilder 타입이고, Set<String>은 String만 받기 때문이다.


📙 예시 (N=4, M=2)

예를 들어, 아래와 같은 입력이 들어왔을 때 수열은 다음과 같다.

  • 입력

    4 2
9 7 9 1
  • 출력

    1 7
1 9
7 1
7 9
9 1
9 7
9 9


👩‍💻 전체 코드

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] nums;
    static boolean[] visited;
    static Set<String> set = new LinkedHashSet<>(); // LinkedHashSet써주기

    static void dfs(int depth){
        StringBuilder sb = new StringBuilder();
        if(m==depth){
            for(int val:arr){
                sb.append(val).append(" ");
            }
            set.add(sb.toString());
            return;
        }


        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                arr[depth] = nums[i]; // 입력된 숫자 넣어주기
                dfs(depth+1);
                visited[i] = false;
            }
        }

    }

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

        n = Integer.parseInt(st.nextToken()); // visited 크기
        m = Integer.parseInt(st.nextToken()); // arr 크기

        nums = new int[n];
        arr = new int[m];
        visited = new boolean[n];

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

        dfs(0);

        for(String s:set){
            System.out.println(s);
        }
    }
}


10. N과 M (10) - 입력 수열 조합 (중복 제거)

📘 문제 설명

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

  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.


📕 문제 해석

이 문제는 입력으로 주어진 수열에서 중복 없이 M개를 고른 조합 을 구하는 문제이다.
이쯤 되면 입력 수열 + 중복 허용 + 중복 제거 패턴이 눈에 익을 것이다.

  • 중복 허용 X
    • visited[] 없이도 start만으로 충분히 처리 가능 -> 백트래킹 구조 자체로 오름차순 필터링 가능하기 때문
  • 오름차순 조건 O
    • 비내림차순(앞 ≤ 뒤)을 만족해야 하므로 start 인덱스를 넘겨준다.
    • for (int i = start; i <= n; i++)로 현재 수 이상부터 탐색
  • 입력 수열 사용
    • nums[] 배열에 주어진 수열을 저장한 뒤, 정렬하여 탐색
  • 중복 제거
    • 입력 수열에 중복된 숫자가 있을 수 있으므로, LinkedHashSet으로 결과 중복을 제거하였다.


📙 예시 (N=4, M=2)

예를 들어, N=4, M=2일 때 가능한 수열은 다음과 같다.

  • 입력

    4 2
9 7 9 1
  • 출력

    1 7
1 9
7 9
9 9


👩‍💻 전체 코드

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] nums;
    static Set<String> set = new LinkedHashSet<>(); // LinkedHashSet써주기

    static void dfs(int start, int depth){
        StringBuilder sb = new StringBuilder();
        if(m==depth){
            for(int val:arr){
                sb.append(val).append(" ");
            }
            set.add(sb.toString());
            return;
        }

        for(int i=start; i<n; i++){
            arr[depth] = nums[i]; // 입력된 숫자 넣어주기
            dfs(i+1,depth+1);
        }
    }

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

        n = Integer.parseInt(st.nextToken()); // visited 크기
        m = Integer.parseInt(st.nextToken()); // arr 크기

        nums = new int[n];
        arr = new int[m];

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

        dfs(0, 0); // nums 배열은 0부터 시작하므로 start=0

        for(String s:set){
            System.out.println(s);
        }
    }
}


11. N과 M (11) - 입력 수열 중복 순열 (중복 제거 없음)

📘 문제 설명

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

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


📕 문제 해석

이 문제는 입력으로 주어진 수열에서 중복을 허용하며 M개를 고른 순열을 구하는 문제이다.

  • 중복 허용 O
    • 같은 수를 여러 번 고를 수 있으므로 visited[]는 사용하지 않는다.
  • 오름차순 조건 X
    • 오름차순일 필요는 없기 때문에 start 인덱스도 사용하지 않는다.
    • 단순히 i = 0부터 반복하여 모든 경우의 수를 탐색한다.
  • 입력 수열 사용
    • nums[] 배열에 주어진 수열을 저장한 뒤, 정렬하여 탐색
  • 중복 제거
    • 입력 수열에 중복된 숫자가 있을 수 있으므로, LinkedHashSet으로 결과 중복을 제거하였다.


📙 예시 (N=4, M=2)

예를 들어, N=4, M=2일 때 가능한 수열은 다음과 같다.

  • 입력

    4 2
9 7 9 1
  • 출력

    1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9


👩‍💻 전체 코드

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] nums;
    static Set<String> set = new LinkedHashSet<>(); // LinkedHashSet 써주기

    static void dfs(int depth){
        StringBuilder sb = new StringBuilder();
        if(m==depth){
            for(int val:arr){
                sb.append(val).append(" ");
            }
            set.add(sb.toString());
            return;
        }

        for(int i=0; i<n; i++){
            arr[depth] = nums[i]; // 입력된 숫자 넣어주기
            dfs(depth+1);
        }
    }

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

        n = Integer.parseInt(st.nextToken()); // visited 크기
        m = Integer.parseInt(st.nextToken()); // arr 크기

        nums = new int[n];
        arr = new int[m];

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

        dfs(0);

        for(String s:set){
            System.out.println(s);
        }
    }
}


12. N과 M (12) - 입력 수열 중복 조합

📘 문제 설명

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

  • N개의 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.


📕 문제 해석

  • 중복 허용 O
    • 같은 수를 여러 번 고를 수 있으므로 visited[]는 사용하지 않는다.
  • 오름차순 조건 O
    • 비내림차순(앞 ≤ 뒤)을 만족해야 하므로 start 인덱스를 넘겨준다. (dfs(i, depth + 1))
    • for (int i = start; i < n; i++) 형태 현재 수 이상만 탐색
  • 입력 수열 사용
    • nums[] 배열에 주어진 수열을 저장한 뒤, 정렬하여 탐색
  • 중복 제거
    • 입력 수열에 중복된 숫자가 있을 수 있으므로, LinkedHashSet으로 결과 중복을 제거하였다.


📙 예시 (N=4, M=2)

예를 들어, N=4, M=2일 때 가능한 수열은 다음과 같다.

  • 입력

    4 2
9 7 9 1
  • 출력

    1 1
1 7
1 9
7 7
7 9
9 9


👩‍💻 전체 코드

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] nums;
    static Set<String> set = new LinkedHashSet<>(); // LinkedHashSet 써주기

    static void dfs(int start, int depth){
        StringBuilder sb = new StringBuilder();
        if(m==depth){
            for(int val:arr){
                sb.append(val).append(" ");
            }
            set.add(sb.toString());
            return;
        }

        for(int i=start; i<n; i++){
            arr[depth] = nums[i]; // 입력된 숫자 넣어주기
            dfs(i, depth+1);
        }
    }

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

        n = Integer.parseInt(st.nextToken()); // visited 크기
        m = Integer.parseInt(st.nextToken()); // arr 크기

        nums = new int[n];
        arr = new int[m];

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

        dfs(0, 0); // nums 배열은 0부터 시작하므로 start=0

        for(String s:set){
            System.out.println(s);
        }
    }
}


카테고리:

업데이트:

댓글남기기

참고