[BOJ/11328/C++] Strfry

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

문제

strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어낸다. (역자 주 : 여기에서 입력된 문자열과 새로 재배열된 문자열이 다를 필요는 없다.) 두 개의 문자열에 대해, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지 판단하라.

조건

• 입력의 첫 번째 줄은 테스트 케이스의 수 0 < N < 1001 이다.
• 각각의 테스트 케이스는 하나의 줄에 영어 소문자들로만 이루어진 두 개의 문자열이 한 개의 공백으로 구분되어 주어진다. 각각의 문자열의 길이는 최대 1000 이다.

SOL

O(N^2)까지는 괜찮은 문제이다. 두 개의 문자열을 받아서, 두 개의 문자열이 "같은 알파벳"으로 이루어졌는지 확인하면 되는 문제이다. 이때, aabb 와 같이 반복되는 문자열이 입력될 수 있다는 점을 유의해야한다.
(이 점을 간과하고, 최적화하겠다면서, bool형으로 방문배열을 만들었다가 틀렸따..)

즉 , 정직하게 알파벳의 개수까지 반영해야한다 .

#include <bits/stdc++.h>
using namespace std;

void solve(string a, string b)
{
  int words[26] = {};
  for (auto c : a)
    words[c - 'a']++;
  for (auto c : b)
    words[c - 'a']--;
  for (int i : words)
  {
    if (i != 0)
    {
      cout << "Impossible" << '\n';
      return;
    }
  }
  cout << "Possible" << '\n';
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  string a, b;

  for (int i = 0; i < N; i++)
  {
    cin >> a >> b;
    solve(a, b);
  }

  return 0;
}