백준 : 11328번 Strfry(c++)

백준 링크

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

11328번: Strfry

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	10644	4482	3482	40.763%

문제

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"(가능)으로 나타내시오. (따옴표는 제외하고 출력한다.)

예제 입력 1 복사

4
a a
ab ba
ring gnir
newt twan

예제 출력 1 복사

Possible
Possible
Possible
Impossible

코드 풀이

1번 풀이(상대적 느림)

• 입력으로 주어진 테스트 케이스만큼 반복문 실행
• 첫 번째 스트링과 두 번째 스트링의 값을 얻어온다
• 두 스트링을 전부 정렬시킨다
• 두 스트링이 같다면 Possible 출력 다르다면 Impossible출력
  (이때 개행은 꼭 해줘야 한다)

2번 풀이 

 

• 입력으로 주어진 테스트 케이스만큼 반복문 실행
• 소문자 a~z까지 담을 수 있는 배열 선언 및 0 초기화
• 각 String을 반복을 돌면서 word값을 인덱스 카운트를 체크
• 두 벡터가 같다면 Possible 출력 다르다면 Impossible출력
  (이때 개행은 꼭 해줘야 한다)

코드1

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

using namespace std;


int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int Count = 0;
	cin >> Count;

	while (Count--)
	{
		string FirstString, SecondString;
		cin >> FirstString >> SecondString;
		sort(FirstString.begin(), FirstString.end());
		sort(SecondString.begin(), SecondString.end());

		if (FirstString == SecondString)
			cout << "Possible\n";
		else
			cout << "Impossible\n";
	}
}

코드2

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

using namespace std;


int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int Count = 0;
	cin >> Count;

	while (Count--)
	{
		vector<int> vecFirst(26, 0);
		vector<int> vecSecond(26, 0);
		string FirstString, SecondString;
		cin >> FirstString >> SecondString;

		for (auto word : FirstString)
		{
			++vecFirst[word - 'a'];
		}
		for (auto word : SecondString)
		{
			++vecSecond[word - 'a'];
		}

		if(vecFirst == vecSecond)
			cout << "Possible\n";
		else
			cout << "Impossible\n";
	}
}