문제

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

문제접근

여러 가지로 접근해봤는데 전혀 생각이 안났다.
그래서 알고리즘 분류 확인했다.

• 브루트포스 알고리즘
• 슬라이딩 윈도우

슬라이딩 윈도우를 보고 나니 방법이 떠올랐다.
1. b를 기준으로 생각(a 기준으로 보는 거랑 똑같다고 생각)
2. b의 갯수만큼인 윈도우를 생각
3. 초기 상태에서 윈도우를 움직인다.
4. 윈도우에 b가 가장 많이 담길 때까지 움직인다.
5. 가장 많이 담긴 상태에서 윈도우 내 a를 바깥 b들과 바꾼다.

코드

from sys import stdin

input = stdin.readline

n = input().rstrip()
len_b = 0
for i in n:
    if i == "b":
        len_b += 1
max = 0
tmp = 0
s = 0
e = s + len_b
for i in range(s, e):
    if n[i] == "b":
        tmp += 1
max = tmp
for i in range(len_b, len(n) + len_b):
    e = i % len(n)
    if n[e] == "b":
        tmp += 1
    if n[e - len_b] == "b":
        tmp -= 1
    if tmp > max:
        max = tmp
print(len_b - max)

for i in n:
    if i == "b":
        len_b += 1

b의 총 갯수 찾기

max : 윈도우 구간 내 최대 b 갯수
tmp : 탐색 중 해당 윈도우 구간의 b 갯수
s : 초기 윈도우 시작점
e : 초기 윈도우 끝

for i in range(s, e):
    if n[i] == "b":
        tmp += 1
max = tmp

첫 윈도우 구간 탐색

for i in range(len_b, len(n) + len_b):
    e = i % len(n)
    if n[e] == "b":
        tmp += 1
    if n[e - len_b] == "b":
        tmp -= 1
    if tmp > max:
        max = tmp

한칸 오른쪽에 있는 알파벳 더하기, 제일 왼쪽 알파벳 윈도우에서 빼기 반복

복잡도 분석

시간 복잡도

초기 윈도우를 탐색하고 선형적으로 탐색한다.
다중 반복문이 없으므로
O(n)
채점결과 : 44ms

공간 복잡도

탐색하는 윈도우를 실제로 리스트로 저장하지 않는다.
tmp, max, s, e와 같은 변수는 복잡도에서 상수로 생각할 수 있으므로
O(n)
채점 결과 : 31120KB

학습포인트

for i in range(len_b, len(n) + len_b):

탐색 범위 설정을 잘못했다.
abab인 경우를 예시로 생각하다가
윈도우(인덱스)
초기 : ab(0,1)
i = 2 : ba(1,2)
i = 3 : ab(2,3)
i = 4 : ab(3,0)
까지 탐색하니까 range(len_b, len(n)+1)이구나! 라고 잘못 생각했다.

단순한 예시를 잘못 일반화한 문제...
범위를 항상 잘 생각하자.

슬라이딩 윈도우 혹은 투 포인터라는 부분을 어떻게 생각할 수 있을까.
1. 원형이다
정도에서 힌트를 얻을 수 있으려나
처음에 어떻게 접근해야 할지 감이 안와서 힘들었다.