[C++] 백준 13019번: A를 B로

🔗 문제

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

13019번: A를 B로

 

🖍 풀이

 

solve() : A와 B의 구성요소 유무로 가능성 확인

• A와 B의 문자열 길이가 같아야 한다.
• A와 B를 정렬했을 때 서로 같아야 한다. 같은 문자 구성이라면 정렬했을 때 똑같다!
  • 문자열 길이가 짧아서 정렬해도 시간 초과 없음

 

solve2()

A와 B 문자열을 뒤에서부터 같은지 확인하며 다른 문자열이 나오면 ++result

• 각 A, B의 뒤를 가르키는 포인터 aptr, bptr를 만들고 서로 같을 때까지 aptr을 왼쪽으로 이동
• 두 포인터 중 하나라도 문자열 범위를 벗어나면 종료하고 result를 출력한다.

 

먼저 solve()로 구성이 아예 불가능한지 확인한 후, solve2()를 돌려주었다.

 

💾  소스

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

bool solve(std::string A, std::string B) // 일부러 복사 파라미터 사용
{
    if(A.size() != B.size()) // 길이 확인
        return false;
    
    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());
    
    for(int i=0; i<A.size(); ++i) // 문자 구성 확인
    {
        if(A[i] != B[i])
        {
            return false;
        }
    }
    
    return true;
}

int solve2(std::string& A, std::string& B)
{
    int result = 0;
    int aptr, bptr;

    aptr = bptr = A.length()-1;
    
    while(bptr >=0 && aptr >=0)
    {
        if(A[aptr] != B[bptr])
        {
            --aptr;
            ++result;
        }
        else
        {
            --aptr; --bptr;
        }
    }

    return result;
}

int main()
{
    std::string A, B;
    std::cin >> A >> B;
    
    
    std::cout << (solve(A, B) ? solve2(A, B) : -1);
    
    return 0;
}