[백준] 1759. 암호 만들기

백준 문제 풀이

 

[백준] 1759. 암호 만들기

1759번: 암호 만들기

 

---

문제 해석

입력으로 L,C가 주어지고, C개의 문자들이 주어진다.

이 중 L개를 골라서 최소 한 개의 모음과 두 개의 자음으로 이루어진 암호를 모두 출력하는 문제이다.

 

풀이

이 문제는 순열을 이용해서 모든 경우를 다 구하면서 조건에 맞는 것만 출력해 주는 식으로 풀었다.

	// 1. 입력받는 부분
	int input_l, input_c;		// 3<=input_l<=input_c<=15
	cin >> input_l >> input_c;

	for (int i = 0; i < input_c; i++)
	{
		cin >> input_alpabets[i];
	}

	// 2. 입력받은 input_alpabets을 정렬
	sort(input_alpabets, input_alpabets + input_c);

	// 3. is_selected 배열을 설정해 둔 뒤, prev_permutation을 통해 모든 경우를 구해봄
	for (int j = 0; j < input_l; j++)
	{
		is_selected[j] = 1;
	}
	for (int k = input_l; k < input_c; k++)
	{
		is_selected[k] = 0;
	}

입력으로 input_c개의 알파벳 소문자가 들어오면 input_alpabets배열에 하나씩 저장한다. 그 후 sort를 통해 정렬을 해 주었다. (sort로 숫자뿐만 아니라 알파벳도 정렬이 가능하다)

그리고 i번째 문자가 선택되었는지 아닌지를 저장할 배열인 is_selected에 input_l개 만큼 1을 넣고, 나머지는 0을 넣어 준다. 예시와 같이 a t c i s w가 들어왔다면 a c i s t w로 정렬되고, 4개의 알파벳으로 암호를 만든다고 했으니 is_selected에는 1 1 1 1 0 0이 들어갈 것이다.

이제 prev_permutation을 통해 is_selected의 경우들을 구한다. 111100부터 시작해서 001111까지 구할 것이다.

 

다른 문제랑 조금 다른 점이라면, "최소 한 개의 모음과 두 개의 자음으로 이루어진" 이라는 조건이 있기 때문에 print부분에서 자음/모음 개수를 세면서 조건에 맞는 경우들만 출력을 할 수 있게 해 주었다.

char input_alpabets[15];			// 입력으로 받은 알파벳의 배열
int is_selected[15];			// i번째 알파벳이 선택되었는지 여부를 저장할 배열

void PrintArray(int input_l) {
	// 입력받은 알파벳을 is_selected에 따라서 출력
	int num_of_vowels = 0;
	int num_of_consonants = 0;

	string output = "";
	for (int i = 0; i < input_l; i++)
	{
		// 한 글자씩 읽으면서 자음과 모음의 개수를 셈
		if (is_selected[i]) {
			if (input_alpabets[i] == 'a' || input_alpabets[i] == 'e' || input_alpabets[i] == 'i' || input_alpabets[i] == 'o' || input_alpabets[i] == 'u') {
				num_of_vowels++;
			}
			else {
				num_of_consonants++;
			}
			output.push_back(input_alpabets[i]);
		}
	}

	if (num_of_vowels >= 1 && num_of_consonants >= 2) {
		// 최소 한 개의 모음과 두 개의 자음으로 구성되어 있다는 조건이 있으므로, 이를 확인하고 조건에 맞을 경우에만 출력함
		cout << output << "\n";
	}

	return;
}

string output을 만들어서 한 글자씩 읽은 것들을 저장해 둘 수 있게 하였고, 읽으면서 자음인지 모음인지 개수를 체크하도록 하였다.

마지막에 조건을 추가해서 만족할 때에만 출력하도록 한다.

 

전체 소스코드 (Github)