링크
https://www.acmicpc.net/problem/15663
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n, m, input;
vector <int> res;
map <int, int > seq; // n개의 자연수를 저장할 맵
void solve(int cur) {
if (cur == m) {
for ( int i = 0; i < res.size(); i++) {
cout << res[i] << ' ';
}
cout << '\n';
return;
}
for (auto i = seq.begin(); i != seq.end(); i++) { //빈도수와 상관 없이 key개수만큼 돌게 된다.
if (i->second > 0) { //빈도가 남아있다면 같은 값이라도 상관없다.
i->second--; //빈도 하나 줄이기.
res.push_back(i->first); //key값 삽입
solve(cur + 1);
res.pop_back();//res에 넣었던거 제거
i->second++; //탐색하고 나온거니까 다시 빈도 올려주기
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> input;
if (seq.find(input) == seq.end()) { //map은 find해서 해당 key값이 없다면 마지막 iterator을 리턴함.
seq.insert({ input, 1 });
}
else
seq[input]++;//이미 key값이 있다면 value 값은 +1한다.
}
//map은 자동으로 key기준 오름차순되므로 정렬할 필요 없다.
solve(0);
}설명
⭐⭐⭐ 이전 문제들과 크게 달라진 부분이 있다. 지금까지는 N개의 자연수는 모두 다른 수이다.라는 조건이 있었지만 이번 문제는 이런 조건이 없다.
중복 가능한 N개의 값이 주어진다. 아니다, 엄밀히 말하면 중복이 아닌거 같다. 같은 값이 여러번 나올 수 있는 N개의 값이 주어진다. 한 개의 값이 중복되는게 아니라 같은 값이 여러번 나올 수 있다. 한 원소를 중복해서 사용할 수 있다는 게 아니라 같은 값이 여러번 나올 수 있다.
📌 문제 조건: 중복되는 수열을 여러번 출력하면 안된다.
즉, 일반적인 순열일 경우, 같은 값을 여러번 입력 받았을 때 각각의 같은 값을 서로 다른 값으로 보고 중복된 수열이 나올 것이다.
그렇다고 마냥 여러번 입력된 같은 값을 하나 빼고 제거하는건 답이 될 수 없다. 중복된 수열이 출력 안되는 것이지, 여러번 입력된 같은 값이 여러번 출력 안되는 건 아니다. 같은 순열이 없다면 얼마든지 같은 값이 여러번 나올 수 있다.
⭐ 따라서 반복문은 여러번 입력받은 값을 하나의 값으로 보고 반복을 돌리되,같은 수를 몇번 입력받았는지 빈도를 if조건으로 걸어둬서 빈도만 남아있다면 여러번 같은 값을 나올 수 있게 해야한다.
입력받을때 map으로 받는다. 이유는 다음과 같다.
- map의 key는 중복되지 않는다.
- map은 key값은 기준으로 자동으로 오름차순한다.
- value값에 빈도수를 넣는다.
- 반복문에서 key 개수 만큼 돈다.
따라서 같은 값이 여러개있어도 key개수만큼만 돌게 되고
빈도수와 m에 따라 같은 값이 얼마든지 중복되서 나올 수도 있다.
똑같은 순열이 나오지 않는다.
어려웠다👀
이전 문제들과의 정확한 차이를 알아야겠다.
source : https://hanbi97.tistory.com/115
