<백준 알고리즘>1522번 슬라이딩 윈도우

백준 1522번

접근 방법

1. 처음엔 dfs나 bfs를 이용하여 a와 b를 스왑한 경우에 대하여 횟수를 측정하는 방식으로 접근했다. b가 a와 스왑되는 위치에 대하여 브루트 포스를 진행하며 동시에 dfs를 해야하니 어디서 멈출지도 애매하고 시간 초과가 날 것이라는 생각이 들었다.
2. 그래서 첫 b와 끝에있는 b안에 있는 경우에 대해서 그 안에있는 a를 세는 방법으로 생각했는데 이러면 항상 최소의 경우만 나오는 것이 아니기 때문에 다른 방법을 생각해 보았다.
3. 2번과 비슷한 방식으로 b의 개수를 범위로 하는 윈도우를 이용하여 그 안에 있는 a의수(= 스왑해야할 경우의 수)를 세서 하는 것이 좋을 것 같다는 생각이 들었다.

코드

유의할 점은 처음과 끝이 인접한 것이기에 여기에 대한 경우도 계산해 주어야 한다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;


string str;
int bCnt = 0;


int main()
{
    cin >> str;


    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'b')
        {       
  
            bCnt++;
        
        }

    }
   
    int minVal = 1e9;

    for (int i = 0; i < str.size(); i++)
    {
        int cnt = 0;
        int Idx = i;
        int bcnt = bCnt;
        
        while(bcnt--)
        {

            if (str[Idx] == 'a')
                cnt++;

            if (Idx == str.size() - 1)
                Idx = 0;
            else
                Idx++;
        }

        minVal = min(cnt, minVal);
    }

  
 

    cout << minVal;

    return 0;
}