[BOJ] #1522 문자열 교환

시간 제한	메모리 제한	정답 비율
2 초	128 MB	43.590%

1522번: 문자열 교환

 

문제

a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.

이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.

예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.
첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.

 

해결

key point, 슬라이딩 윈도우

• 연속된 b를 만들기 위해서 입력으로 주어진 문자열에서 b개의 개수를 세어 저장한다. → size
• 이 문제에서 문자열은 원형이다. 따라서 문자열을 한번 더 이어 붙여준다 → str += str;
  • 이렇게 되면, 0부터 str.length()까지 보면서, 슬라이딩 윈도우로 윈도우 크기(L)만큼 볼 때 원형의 모양으로 전부 확인할 수 있다.
• 여기서 윈도우 크기는 바로 size가 된다.
• 이제, 0 부터 str.length()까지 모든 i에 대해서 str[i]가 'b'라면 queue에 인덱스 i를 넣어준다.
  • b가 존재한 위치와 동시에 현재 보고있는 구간에 있는 b의 개수를 바로 알 수 있다. → q.size()
  • i - q.front() 가 size 보다 같거나 크다면, 구간의 범위를 넘어선 것이므로 queue에서 제거한다. → q.pop()
• 교환 횟수의 최솟값을 구하기 위해서는 min함수를 이용해서, size - q.size()의 최솟값을 구한다.
  • 우리가 구하고자 하는 size는 연속된(되어야하는) b의 개수이며, q.size()는 현재 보고 있는 구간의 b의 개수이다.
  • size - q.size() 의 값이 바로 구간에 있는 a의 개수가되고 즉, 교환 횟수가 된다.
  • 따라서 모든 구간에 대해서 size - q.size()의 최솟값을 구한다면 정답을 찾을 수 있다.

 

코드

메모리	시간
2020 KB	0 ms

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
string str;
int main() {
    cin >> str;
    int size = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == 'b') size++;
    }
    str += str;    
    int ans = size;
    queue<int> q;
    for (int i = 0; i < str.length(); i++) {
        if (!q.empty() && i - q.front() >= size) q.pop();
        if (str[i] == 'b') q.push(i);
        ans = min(ans, size - (int)q.size());
    }
    printf("%d", ans);
    return 0;
}