백준 1522 - 문자열 교환 (C++)

 

 

주어진 문자열에서, 두 문자를 바꿔가며 a가 연속된 문자열을 만들면 된다.

예를 들어, abbababa라는 문자열이 있다고 치자.

 

이 문자열에서 4번째 문자와 7번째 문자를 바꿔보자.

abbbbaaa가 된다.

 

일반적인 문자열이라면, a가 연속되지 않는다고 생각할 수 있다.

하지만, 이 문자열은 원형으로 이어져 있다고 가정되어 있으므로 4개의 a는 모두 이어져 있다고 볼 수 있다.

 

두 문자를 바꾸는 '교환'을 최소 몇 번 해야 a가 모두 연속된 문자열이 될 수 있는지 탐색하여 최소 교환 횟수를 출력하면 된다.

 

문제 풀이

 

이 문제는 아이디어를 구하는 것이 다소 어려운 문제였다.

본인은 슬라이딩 윈도우 기법을 활용하여 문제를 해결하였다.

 

먼저, 아래 그림을 보자.

 

이렇게 문자열이 주어졌다고 가정해보자.

이 때, 이 문자열에는 a가 총 3개, b가 총 5개 포함되어 있다.

 

그렇다면, 이렇게 상황을 생각해 볼 수 있지 않을까?

문자열에서 위처럼 a개수와 동일한 3개의 공간을 확보한 뒤에, 거기에 a를 가득 채우면 나머지 공간은 b로 가득 찰 것이고, 결국 a가 연속된 문자열이 완성되는게 아닐까?

이렇게, 어떤 위치를 잡든 a개수만큼 공간을 할당한 뒤 a로 가득채우면 나머지 공간은 b로 가득 찰 것이고, 결국 a가 연속된 형태의 문자열을 만들 수 있을 것이다.

 

그런데, 굳이 새로운 문자열을 만들 필요도 없고, 아래와 같이 만들 수 있을 것이다.

기존 문자열에서 a개수만큼의 공간을 탐색한 뒤, 안에 있는 b를 전부 밖의 a랑 바꿔버린다면?

이렇게 a가 연속된 형태의 문자열이 완성된다.

다른 위치라고 해도, 마찬가지로 a가 연속된 문자열을 만들 수 있다.

 

이를 토대로 생각해본다면, a로 모두 바꿔버리기로 마음 먹은 구간에 b가 2개있다면, 총 2번의 교환을 통해 a가 연속된 문자열을 만들 수 있다는 뜻일 것이다.

 

그렇다면, 문자열 내에서 a개수만큼의 범위를 모두 탐색하여 b가 가장 적게 들어있는 구간을 찾는다면?

해당 구간에 속한 b의 개수가 최소 교환 횟수가 될 것이다.

 

아래 과정을 보자.

처음에 3칸의 구간을 탐색해보면,b가 2개 속해있다. 이 때, 교환횟수는 2회가 된다.

이 구간엔 b가 3개 속해있으므로, 교환 횟수는 3회가 된다.

이 구간 역시 마찬가지로 교환 횟수는 3회가 된다.

 

쭉 가서, 마지막 구간을 보자.

이 구간에선, b가 1개밖에 존재하지 않는다. 즉 교환 횟수는 1회가 된다.

그러므로, 이 문자열에서 연속된 a를 만들기 위해선 최소 교환횟수는 1회라고 할 수 있다.

 

하지만, 이렇게만 탐색하면 한가지 문제가 있다.

위에서 구한 방식대로, 위의 문자열에서 최소 교환 횟수를 탐색해보면 1회가 나온다.

a의 개수와 동일한 5칸으로 이루어진 구간중에 b의 최소 개수는 1개이기 때문이다.

 

그런데, 문제를 생각해보면 해당 문자열은 단 1번도 바꾸지 않아도 이미 a가 연속된 문자열이다.

그렇기 때문에, 우리는 한가지 경우를 더 생각해야 한다.

 

구간에 a를 몰아넣을 경우가 아니라, 구간에 b를 몰아넣는 경우이다.

b의 개수만큼의 구간을 기준으로, 구간에 b를 몰아넣는다고 가정하고 탐색하면 위의 그림처럼 b로 가득찬 구간을 탐지할 수 있다. 이 때, 해당 영역에 속한 a의 개수는 0개이므로 교환 횟수는 0회가 나온다.

 

즉, 구간에 a를 몰아넣는 경우의 최소 교환 횟수와 구간에 b를 몰아넣는 경우의 최소 교환 횟수를 둘 다 구한 뒤에

둘 중에서 최소값을 정답으로 출력해야 하는 것이다.

 

풀이 코드

 

std::string InputStr;
std::cin >> InputStr;

int NumOfA = 0;
int NumOfB = 0;

for (int i = 0; i < InputStr.size(); i++)
{
    if (InputStr[i] == 'a')
    {
        NumOfA++;
    }
    else
    {
        NumOfB++;
    }
}

문자열을 입력받은 뒤, a의 개수와 b의 개수를 각각 세어주고 있다.

 

int Answer1 = 0;
int Answer2 = 0;

이후, 구간에 a를 몰아넣는 경우의 최소 교환횟수를 저장할 Answer1과, 구간에 b를 몰아넣는 경우의 최소 교환횟수를 저장할 Answer2를 선언해주었다.

 

{
    int WindowSize = NumOfA;
    int BCount = 0;

    for (int i = 0; i < WindowSize; i++)
    {
        if (InputStr[i] == 'b')
        {
            BCount++;
        }
    }

    int MinBCount = BCount;

    for (int i = 1; i < InputStr.size() - WindowSize; i++)
    {
        if (InputStr[i - 1] == 'b')
        {
            BCount--;
        }

        if (InputStr[i + WindowSize - 1] == 'b')
        {
            BCount++;
        }

        MinBCount = std::min(MinBCount, BCount);
    }

    Answer1 = MinBCount;
}

 

먼저, A의 개수만큼 WindowSize를 설정해주었다.

(탐색할 구간의 크기이다.)

 

최초에는 0~ WindowsSize - 1까지 b가 몇개 있나 탐색해주었고, 이후 구간을 우측으로 1씩 움직이며, 기존 구간에서 b가 빠졌다면 b의 개수를 빼주고, 새롭게 b가 구간에 추가되었다면 b의 개수를 더해주면서 BCount를 갱신해주었다.

{
    int WindowSize = NumOfB;
    int ACount = 0;

    for (int i = 0; i < WindowSize; i++)
    {
        if (InputStr[i] == 'a')
        {
            ACount++;
        }
    }

    int MinACount = ACount;

    for (int i = 1; i < InputStr.size() - WindowSize; i++)
    {
        if (InputStr[i - 1] == 'a')
        {
            ACount--;
        }

        if (InputStr[i + WindowSize - 1] == 'a')
        {
            ACount++;
        }

        MinACount = std::min(MinACount, ACount);
    }

    Answer2 = MinACount;
}

 

다음은 완전히 동일하게 구간에 b를 몰아넣는 경우의 최소 교환 횟수를 구해주었다.

 

int Answer = std::min(Answer1, Answer2);

std::cout << Answer;

return 0;

 

마지막으로, 둘 중 최소값을 정답으로 출력해주면 끝이다.

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    std::string InputStr;
    std::cin >> InputStr;

    int NumOfA = 0;
    int NumOfB = 0;

    for (int i = 0; i < InputStr.size(); i++)
    {
        if (InputStr[i] == 'a')
        {
            NumOfA++;
        }
        else
        {
            NumOfB++;
        }
    }

    int Answer1 = 0;
    int Answer2 = 0;

    {
        int WindowSize = NumOfA;
        int BCount = 0;

        for (int i = 0; i < WindowSize; i++)
        {
            if (InputStr[i] == 'b')
            {
                BCount++;
            }
        }

        int MinBCount = BCount;

        for (int i = 1; i < InputStr.size() - WindowSize; i++)
        {
            if (InputStr[i - 1] == 'b')
            {
                BCount--;
            }

            if (InputStr[i + WindowSize - 1] == 'b')
            {
                BCount++;
            }

            MinBCount = std::min(MinBCount, BCount);
        }

        Answer1 = MinBCount;      
        
        int WindowSize = NumOfB;
        int ACount = 0;

        for (int i = 0; i < WindowSize; i++)
        {
            if (InputStr[i] == 'a')
            {
                ACount++;
            }
        }

        int MinACount = ACount;

        for (int i = 1; i < InputStr.size() - WindowSize; i++)
        {
            if (InputStr[i - 1] == 'a')
            {
                ACount--;
            }

            if (InputStr[i + WindowSize - 1] == 'a')
            {
                ACount++;
            }

            MinACount = std::min(MinACount, ACount);
        }

        Answer2 = MinACount;
    }

    int Answer = std::min(Answer1, Answer2);

    std::cout << Answer;

    return 0;
}