[ 11328 ] Strfry - array, vector

< array, vector > - < solve등급 >

 

[ 11328 ]

Strfry

C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래밍 언어에서 문자열을 다루는 것은 매우 중요하기 때문에, C 표준 라이브러리는 문자열을 다루는 데에 매우 유용한 함수들을 제공하고 있다 : 그들 중에는 strcpy, strcmp, strtol, strtok, strlen, strcat 가 있다.

하지만, 잘 알려져 있지 않으며, 잘 사용되지도 않는 함수가 하나 있다 : strfry 함수다. strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어낸다. (역자 주 : 여기에서 입력된 문자열과 새로 재배열된 문자열이 다를 필요는 없다.)

두 개의 문자열에 대해, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지 판단하라.

 

:: 입력

입력의 첫 번째 줄은 테스트 케이스의 수 0 < N < 1001 이다.

각각의 테스트 케이스는 하나의 줄에 영어 소문자들로만 이루어진 두 개의 문자열이 한 개의 공백으로 구분되어 주어진다. 각각의 문자열의 길이는 최대 1000 이다.

:: 출력

각각의 테스트 케이스에 대해, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지의 여부를 "Impossible"(불가능) 또는 "Possible"(가능)으로 나타내시오. (따옴표는 제외하고 출력한다.)

---

 

- try 1 

: 알파벳 배열을 만들고 첫 단어에 들어있는 알파벳을 저장한 후에 두번째 단어들의 알파벳이 모두 포함되는지 확인하려고 했음

근데 생각해보니까 

abcd abcde 인 경우에 예외가 발생함

 

  아이디어  

다들 비슷한 방식으로 풀었음 !

근데 두 문자열의 길이가 다른 경우 바로 예외 처리를 해주는 부분이 있었음

 

  try1  코드  

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define endl "\n"

int res[1001] = { 0, };

int main() {
	
	string q1, q2;

	int n = 0;
	int indx = 0;
	cin >> n;

	while (n != indx) {
		cin >> q1 >> q2;

		int alpa[26] = { 0, };

		for (int i = 0; i < q1.length(); i++) {
			alpa[q1[i] - 97]++;
		}

		for (int i = 0; i < q2.length(); i++) {
			if (alpa[q2[i] - 97] == 0) { res[indx] = 1; break; }
		}

		indx++;
	}

	for (int i = 0; i < n; i++) {
		if (res[i] == 0) {
			cout << "Possible" << endl;
		}
		else cout << "Impossible" << endl;
	}
}

 

- try 2

: 첫 단어만 저장하면 예외가 발생한다는 걸 알아서 

두번째 단어도 저장해서 저장된 배열을 비교함 ! 이 앞의 문제랑 같은 방식으로 비교해서

알파벳의 개수가 다를 경우 결과를 저장하는 배열에 1을 넣어줌

 

  정답  코드  

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define endl "\n"

int res[1001] = { 0, };

int main() {
	
	string q1, q2;

	int n = 0;
	int indx = 0;
	cin >> n;

	while (n != indx) {
		cin >> q1 >> q2;

		int alpa1[26] = { 0, };
		int alpa2[26] = { 0, };

		for (int i = 0; i < q1.length(); i++) {
			alpa1[q1[i] - 97]++;
		}

		for (int i = 0; i < q2.length(); i++) {
			alpa2[q2[i] - 97]++;
		}

		for (int i = 0; i < 26; i++) {
			if (alpa1[i] != alpa2[i]) {
				res[indx]++; break;
			}
		}

		indx++;
	}

	for (int i = 0; i < n; i++) {
		if (res[i] == 0) {
			cout << "Possible" << endl;
		}
		else cout << "Impossible" << endl;
	}
}