[C++] 백준 1759번: 암호 만들기

www.acmicpc.net/problem/1759

1759번: 암호 만들기

처음엔 그냥 next_permutation을 사용하고 l개 만큼 만 출력하는 식으로 해결하려 했지만 메모리 초과가 나서 시간이 꽤 걸렸던 문제이다.

 

메모리 초과의 문제는 정확힌 모르겠지만 string의 메모리가 제대로 해제가 되지 않았거나 벡터에 중복값들이 들어가서 그랬던 것 같다.

 

계속 시행착오를 겪다가 그냥 정렬을 해놓고 0과 1로 이루어진 임시 벡터를 사용해 조합을 한다면 어차피 정렬은 되있기에 자음과 모음의 개수만 체크해주면 되는 문제였다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

vector<string> s;

int main() {
	int l, c, check1 = 0, check2 = 0;
	string a = "";
	cin >> l >> c;
	vector<char> v(c);
	vector<int> temp;
	for (int i = 0; i < c; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < c; i++) {
		if (i < l) {
			temp.push_back(0);
		}
		else {
			temp.push_back(1);
		}
	}
	sort(v.begin(), v.end());
	do {
		a = "";
		check1 = 0, check2 = 0;
		for (int i = 0; i < c; i++) {
			if (temp[i] == 0) {
				a += v[i];
			}
		}
		for (int i = 0; i < a.size(); i++) {
			if (a[i] == 'a' || a[i] == 'e' || a[i] == 'i' 
				|| a[i] == 'o' || a[i] == 'u') {
				check1++;
			}
			else {
				check2++;
			}
		}
		if (check1 >= 1 && check2 >= 2) {
			s.push_back(a);
		}
	} while (next_permutation(temp.begin(), temp.end()));

	for (int i = 0; i < s.size(); i++) {
		cout << s[i] << "\n";
	}

	return 0;
}