[백준][C++] 11328번 Strfry

Strfry

문제 링크

Strfry

분석

첫째 줄에 테스트 케이스의 개수가 주어집니다.

각 테스트 케이스는 한 줄에 두 개의 문자열이 주어집니다.
해당 문자열은 공백으로 구분되며, 소문자로만 이루어져 있습니다.

첫 문자열을 무작위로 재배열 하여 두 번째 문자열을 만들어낼 수 있을 경우 Possible을 출력하고, 만들어 낼 수 없을 경우 Impossible을 출력해주어야합니다.

무작위로 재배열하여 만들 수 있는 가능성은 첫 번째 문자열과 두 번째 문자열의 구성 요소가 모두 같아야 합니다.
예를 들어, ring와 gnir는 모두 같은 글자를 가지고 있기 때문에 재배열하여 만들어낼 수 있는 문자열이 됩니다.
그러나, newt와 twan는 두 번째 문자열에 e가 없고, a가 있기 때문에 재배열하여 만들어낼 수 없는 문자열입니다.

풀이

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

// 문자열의 구성 요소가 같은지 확인하여 결과를 반환하는 함수
bool CharacterCountCheck(std::string first, std::string second)
{
    std::vector<int> firstCharacterCount(26, 0);
    std::vector<int> secondCharacterCount(26, 0);

    for (int i = 0; i < first.length(); ++i)
    {
        int CharacterIndex = first[i] - 'a';
        ++firstCharacterCount[CharacterIndex];
    }

    for (int i = 0; i < second.length(); ++i)
    {
        int CharacterIndex = second[i] - 'a';
        ++secondCharacterCount[CharacterIndex];
    }

    for (int i = 0; i < firstCharacterCount.size(); ++i)
    {
        if (firstCharacterCount[i] != secondCharacterCount[i])
        {
            return false;
        }
    }

    return true;
}

int main()
{
    int CaseCount;
    std::cin >> CaseCount;

	// 케이스 횟수만큼 반복
    for (int i = 0; i < CaseCount; ++i)
    {
        std::string first, second;
        std::cin >> first >> second;

        bool bIsPossible = CharacterCountCheck(first, second);

        if (bIsPossible)
        {
            std::cout << "Possible" << std::endl;
        }
        else
        {
            std::cout << "Impossible" << std::endl;
        }
    }
}

성능 요약

시간 복잡도는 $O(n \times l)$입니다.

• 테스트 케이스만큼 반복하는 반복문 $O(n)$
• 문자열의 길이만큼 반복하는 반복문 $O(l)$
• 글자 개수를 비교하는 반복문 $O(26) \approx O(1)$
• $O(n) \times O(l) + O(1)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

메모리: 2024 KB

시간: 56 ms