[슬라이딩 윈도우] 문자열 교환 - 백준 1522번

1522번: 문자열 교환

풀이

EX) aabbaaabaaba , (n = 12)
a를 연속으로 한다 = b를 연속으로 한다.
최솟값 -> 그리디 or 모든 경우의 수를 구하고 그 중 최솟값

a의 갯수만큼 연속되어야 한다 -> 8개
aaaaaaaabbbb 이렇게 만들어야 한다.

모든 경우는 똑같다. 하지만 어떻게 묶어야 교체 횟수가 적은지 찾는다.
[aabbaaab]aaba -> 3개 교체
[abbaaaba]abaa -> 3개 교체
[bbaaabaa]baaa -> 3개 교체
[baaabaab]aaab -> 3개 교체
[aaabaaba]aabb -> 2개 교체
[aabaabaa]abba -> 2개 교체
[abaabaaa]bbaa -> 2개 교체
[baabaaab]baaa -> 3개 교체
[aabaaabb]aaab -> 3개 교체
[abaaabba]aaba -> 3개 교체
[baaabbaa]abaa -> 3개 교체
[aaabbaaa]baab -> 2개 교체
= 12번 (n)
-> 최소 2번 교체가 필요

1. 8개씩 묶을 때 length를 넘어가는 경우 앞자리로 돌아와야 한다.
   • length를 넘지 않는 경우
   • substring (i, 8) : i번 index부터 8개씩 묶기 - 넘어가는 경우
   • substr(i) : i번부터 ~ 끝까지
   • • substr(0, (i + aCount) - s.length()) : 앞에꺼를 붙이기
       • (i + aCount) - s.length(): 남은 개수
2. count함수를 통해 window 내 바꿔야 할 ‘b’의 개수를 체크 = 교체 회수
3. min 함수로 최솟값 구하기

최적화

1. a의 개수 세기

기존 코드

int aCount = 0;
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == 'a') aCount++;
    }

새 코드

b의 개수를 샐 때 처럼 count 함수를 사용한다.

int aCount = count(s.begin(), s.end(), 'a'); 

어차피 같은 O(n) 이지만 코드 간결성이 좋다!

2. 원형 문자열 처리

기존 코드

if(i + aCount > s.length()) {
    window = s.substr(i);
    window += s.substr(0,  (i + aCount) - s.length());
} else {
    window = s.substr(i, aCount); // 0 ~ 8 -> 1 ~ 8
}        

문자열을 수동으로 처리해야 하기 때문에 코드가 더 복잡하고 추가적인 복사 작업이 발생합니다.

새코드

s += s;  // 문자열을 두 번 이어붙여 원형 처리

코드는 더 단순해지고 처리 속도가 빨라집니다.

ex) aabbaaabaaba

⇒ aabbaaabaaba-aabbaaabaaba

3. 슬라이딩 윈도우

기존코드

for(int i = 0; i < s.length(); i++) {
    if(i + aCount > s.length()) {
        window = s.substr(i);
        window += s.substr(0,  (i + aCount) - s.length());
    } else {
        window = s.substr(i, aCount); // 0 ~ 8 -> 1 ~ 8
    }
    int result = count(window.begin(), window.end(), 'b');
    min_value = min(min_value, result);
}

매번 window 문자열을 슬라이싱하고 count 함수를 사용하여 ‘b’의 개수를 세고 있습니다. 이 과정은 매번 O(aCount) 시간 복잡도가 발생하며, 이 작업을 s.length() 만큼 반복합니다. 결과적으로 전체 시간 복잡도는 O(n * aCount)

새코드

// 첫 번째 윈도우에서 b의 개수 세기
int bCount = 0;
for(int i = 0; i < aCount; i++) {
    if(s[i] == 'b') bCount++;
}

int min_value = bCount;

// 슬라이딩 윈도우로 최소 교환 횟수 찾기
for(int i = 1; i < s.length() / 2; i++) {
    if(s[i - 1] == 'b') bCount--;
    if(s[i + aCount - 1] == 'b') bCount++;
    
    min_value = min(min_value, bCount);
}

첫 번째 윈도우에서 b의 개수를 구한다. ⇒ min_value를 구하기 위함

• aCount로 구하는 이유는 aCount == 슬라이딩 윈도우의 크기

i가 0번째의 경우는 구했으니 i = 1 부터 윈도우를 슬라이딩하기 시작한다.

s는 두개를 합쳤으니 s.length()의 절반까지 실행, i가 (s.length() / 2 + 1)이 된다면 원점으로 돌아온다.

• aabbaaabaaba[aabbaaab]aaba

[aabbaaab] 의 경우 b의 개수는 3개 → 슬라이딩 후 → [abbaaaba]

• b의 개수는 맨 앞이 ‘b’라면 window 안의 개수가 하나 줄어들고
  • if(s[i - 1] == 'b') bCount--;
• 맨 뒤에 새로 들어온 글자가 ‘b’라면 window 안의 b의 개수는 하나 늘어난다.
  • if(s[i + aCount - 1] == 'b') bCount++;

⇒ O(n) 시간 안에 처리

코드

https://github.com/KimGyeongLock/CodingTest/blob/main/1522.cpp