풀이 소요시간 : 30분 내외
풀이 시간은 30분이나 정석적인 풀이방법은 아니였다. 중복수열을 체크하는 과정에서 야매 방식을 사용했다고 생각했기에 문제를 풀고나서도 기분이 썩 깔끔하지는 않았다. 이후 정석적인 방법을 공부하고 포스팅을 남긴다.
내가 사용한 접근 방법
중복을 체크하는 과정에서 Map 을 사용하여 Unique 한 String 값을 만들어버렸다.
예를 들어, [3, 1, 44, 3] 의 수열이 있다면 "3 1 44 3" 라는 String 을 만들어 Map 에 저장하고 Count 를 기록한 것이다. 논리 자체에는 오류가 없기에 정답 처리가 되었다. 하지만 리팩토링이 필요하다고 생각했다.
정석적인 접근 방법
탐색(DFS) 과정에서 마지막으로 추가한 항이 다른 것을 보장하면 중복 수열의 발생을 방지할 수 있다. 예를 들어서 [1, 3][1, 7] [1, 9][1, 9] 의 경우 마지막 두 개의 수열은 마지막 추가 항이 '9' 로 같기때문에 중복 수열이 발생한다.
그렇다면 [1, 3, 7, 7] 과 [1, 4, 7, 7] 처럼 마지막 추가 항은 같지만 다른 수열인 경우는 어떻게 된걸까? 사실 위의 두 수열은 마지막 추가 항이 같아보이지만 탐색 당시 2번째 원소의 입장에서 보면 마지막 추가 항은 3 과 4 다. 따라서 추가 항은 서로 다르다.
따라서 탐색 과정에서 마지막으로 추가한 항의 중복을 방지하는 조건을 추가하면 중복 수열은 절대로 발생하지 않는다.
전체 코드(Map을 사용한 중복 체크)
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<algorithm>
using namespace std;
int N, K;
int Map[9];
int Visit[9];
vector<int> Vector;
map<string, int> m;
void Fast_IO() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void Input() {
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> Map[i];
}
}
bool Check_Duplicate() {
string str = "";
for (int i = 0; i < Vector.size(); i++) {
str += to_string(Vector[i]);
str += ' ';
}
if (m[str] > 0) {
return false;
}
else {
m[str]++;
return true;
}
}
void Dfs(int count) {
if (count == K) {
if (Check_Duplicate() == true) {
for (int i = 0; i < Vector.size(); i++) {
cout << Vector[i] << ' ';
}
cout << '\n';
}
return;
}
for (int i = 1; i <= N; i++) {
if (Visit[i] == 1) continue;
Visit[i] = 1;
Vector.push_back(Map[i]);
Dfs(count + 1);
Visit[i] = 0;
Vector.pop_back();
}
}
int main() {
Input();
sort(Map + 1, Map + 1 + N);
Dfs(0);
}전체 코드(리팩토링)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, K;
int Map[9];
int Visit[9];
vector<int> Vector;
void Fast_IO() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void Input() {
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> Map[i];
}
}
void Dfs(int count) {
if (count == K) {
for (int i = 0; i < Vector.size(); i++) {
cout << Vector[i] << ' ';
}
cout << '\n';
return;
}
int last = -1;
for (int i = 1; i <= N; i++) {
if (Visit[i] == 1 || Map[i] == last) continue;
Visit[i] = 1;
Vector.push_back(Map[i]);
last = Map[i];
Dfs(count + 1);
Visit[i] = 0;
Vector.pop_back();
}
}
int main() {
Input();
sort(Map + 1, Map + 1 + N);
Dfs(0);
}
SSAFY 11th