[BOJ] 1759번 : 암호 만들기

1. problem : 

https://www.acmicpc.net/problem/1759

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int L, C; 
vector<char> words;
vector<string> ans; 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> L >> C; 
	for (int i = 0; i < C; i++) {
		char x; 
		cin >> x; 
		words.push_back(x);
	}
	sort(words.begin(), words.end());
	vector<int> v1(words.size(), 0); 
	fill(v1.end() - L, v1.end(), 1); 
	do {
		vector<char> temp; 
		int moum_cnt = 0, jaum_cnt = 0; 
		for (int i = 0; i < v1.size(); i++) {
			if (v1[i]) {
				if (words[i] == 'a' || words[i] == 'e' || words[i] == 'i' || words[i] == 'o' || words[i] == 'u') moum_cnt++;
				else jaum_cnt++;
				temp.push_back(words[i]);
			}
		}
		if (moum_cnt >= 1 && jaum_cnt >= 2) {
			string word(temp.begin(), temp.end());
			ans.push_back(word);
		}
	} while (next_permutation(v1.begin(), v1.end()));
	
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << '\n';
	}
}

모음 >= 1, 자음 >= 2를 만족하면, ans라는 vector에 담고, 출력한다. 이때, next_permutation의 특성상, 초기 setting값이 뒤에 초점을 맞추어, 한번 더 sorting 해주어야 한다. 

 

3. solution 2 :

// Authored by : yongjunleeme
// Co-authored by : -
// http://boj.kr/04b7346a15bd441fb7c815c008682893
#include <bits/stdc++.h>
using namespace std;

int l, c;
int arr[17];
char s[17];
bool isused[17];

bool aeiou(char t){
  return t == 'a' || t == 'e' || t == 'i' || t == 'o' || t == 'u';
}

void func(int k, int st){
  if(k == l){
    bool flag = false;
    int cnt1 = 0;
    int cnt2 = 0;
    for(int i = 0; i < l; i++){
      if(aeiou(s[arr[i]])) cnt1++;
      else cnt2++;
    }
    if(cnt1 >= 1 && cnt2 >= 2) flag = true;

    if(flag){
      for(int i = 0; i < l; i++)
        cout << s[arr[i]];
      cout << "\n";
    }
  }

  for(int i = st; i < c; i++){
      arr[k] = i;
      func(k+1, i+1);
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> l >> c;
  for(int i = 0; i < c; i++) cin >> s[i];
  sort(s, s+c);
  func(0, 0);
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/solutions/1759.cpp

basic-algo-lecture/0x0C/solutions/1759.cpp at master · encrypted-def/basic-algo-lecture

aeiou 검사를 한 후, 모음이 1개 이상, 자음이 2개 이상이면 통과된다. 통과된 문자열은 출력된다. 이후, backTracking 과정을 거친다. 

 

4. solution 3 : 

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/700bd7f11e834635a055fdf0845f4409
#include <bits/stdc++.h>
using namespace std;

int l, c;
char s[20];

bool aeiou(char t){
  return t == 'a' || t == 'e' || t == 'i' || t == 'o' || t == 'u';
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> l >> c;
  for(int i = 0; i < c; i++) cin >> s[i];
  sort(s, s+c);
  vector<int> brute(c);
  for(int i = l; i < c; i++) brute[i] = 1;
  do{
    string ans;
    int cnt1 = 0; // 모음의 수
    for(int i = 0; i < c; i++){
      if(brute[i] == 0){
        ans += s[i];
        if(aeiou(s[i])) cnt1++;
      }      
    }
    if(cnt1 < 1 || l - cnt1 < 2) continue;
    cout << ans << '\n';
  }while(next_permutation(brute.begin(), brute.end()));
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/solutions/1759_1.cpp

basic-algo-lecture/0x0C/solutions/1759_1.cpp at master · encrypted-def/basic-algo-lecture

do {} while (next_permutation)을 활용한 코드. 훨씬 더 잘 짜인 코드이다. 여기서는 0을 포함시키고, 1을 배제한다. 또한, for문을 통해서, vector의 값을 0과 1로 초기화한다. 기억해야겠다.