BOJ 15663 · N과 M (9)

알고리즘 분류 : 브루트 포스  

입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (5) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다.

• 같은 숫자가 여러 개 주어질 수 있으므로, 해당 숫자가 총 몇 개 있는지 세어야 한다.
• 먼저 N개의 숫자가 있는 리스트를 오름차순으로 정렬한다.
• 숫자 리스트에서 처음부터 끝까지 순서대로 이동하면서 각 숫자가 몇 개 있는지 센다.
• 숫자를 세는 방법은 아래와 같다.
• 1. 현재 숫자가 이전 숫자와 같으면, 중복된 숫자이므로 현재 숫자의 개수를 1 증가시킨다.
• 2. 현재 숫자가 이전 숫자와 다르면, 새로운 숫자이므로 숫자 카운트를 1로 둔다. 이전에 카운트한 숫자의 값을 저장한다.

---

C++ 소스코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int a[8], num[8], cnt[8];
vector<int> v;

void count() {
    int number = a[0];
    int counts = 1;
    int len = 0;
    for (int i=1; i<n; i++) {
        if (number == a[i]) {
            counts += 1;
        } else {
            cnt[len] = counts;
            num[len] = number;
            counts = 1;
            number = a[i];
            len += 1;
        }
    }
    cnt[len] = counts;
    num[len] = number;
    n = len;
}

void solve(int depth) {
    if (depth == m) {
        for (auto k : v) printf("%d ", k);
        printf("\n");
        return;
    }
    for (int i=0; i<=n; i++) {
        if (cnt[i]) {
            cnt[i] -= 1;
            v.push_back(num[i]);
            solve(depth+1);
            v.pop_back();
            cnt[i] += 1;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    count();
    solve(0);
    return 0;
}

✓ STL의 set을 이용하여 중복 제거하는 방식으로도 구현할 수 있다.

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

int n, m;
bool check[8];
int a[8];
vector<int> v;
set<vector<int>> s;

void solve(int cnt) {
    if (cnt == m) {
        s.insert(v);
        return;
    }
    for (int i=0; i<n; i++) {
        if (!check[i]) {
            check[i] = true;
            v.push_back(a[i]);
            solve(cnt+1);
            v.pop_back();
            check[i] = false;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    solve(0);
    for (auto k : s) {
        for (auto t : k) printf("%d ", t);
        printf("\n");
    }
    return 0;
}

---

Python 3 소스코드

from sys import stdin, stdout
from collections import Counter
input = stdin.readline
print = stdout.write

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
num, cnt = map(list, zip(*list(Counter(a).items())))
v = []

def solve(c):
    if c == m:
        print(' '.join(map(str, v))+'\n')
        return
    for i in range(len(cnt)):
        if cnt[i]:
            cnt[i] -= 1
            v.append(num[i])
            solve(c+1)
            v.pop()
            cnt[i] += 1

solve(0)

✓ collections에 있는 Counter를 이용하면 각 숫자가 몇 개 있는지 쉽게 셀 수 있다.

✓ set과 permutations를 이용하면 더 간단하게 구현할 수 있다.

from sys import stdin, stdout
from itertools import permutations
input = stdin.readline
print = stdout.write

n, m = map(int, input().split())
a = list(map(int, input().split()))
for k in sorted(set(permutations(a, m))):
    print(' '.join(map(str, k))+'\n')

---

참고

• 백준 온라인 저지 : BOJ 15663
• N과 M (5)