11328 - Strfry

C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다.

사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래밍 언어에서 문자열을 다루는 것은 매우 중요하기 때문에, C 표준 라이브러리는 문자열을 다루는 데에 매우 유용한 함수들을 제공하고 있다.

그들 중에는 strcpy, strcmp, strtol, strtok, strlen, strcat 가 있다.

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

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

C++

1// O(n + m)
2#include <bits/stdc++.h>
3using namespace std;
4
5int main(void) {
6  ios::sync_with_stdio(0);
7  cin.tie(0);
8
9  int n;
10  cin >> n;
11  while(n--) {
12    string a, b;
13    cin >> a >> b;
14
15    int alphaA[26] = {0};
16    int alphaB[26] = {0};
17
18    // O(n + m)  
19    // O(n), n = length of 'a'
20    for(char c : a) ++alphaA[c - 'a'];
21    // O(m), m = length of 'b'
22    for(char c : b) ++alphaB[c - 'a'];
23
24    // O(m), length of 'b'
25    string s = "Possible";
26    for(char c : b) {
27      if(alphaA[c - 'a'] != alphaB[c - 'a']) {
28        s = "Impossible";
29        break;
30      }
31    }
32
33    cout << s << endl;
34  }
35  return 0;
36}