백준 #1522 - [S1] 문자열 교환 : 투포인터

(python3)

1522번: 문자열 교환

 

아이디어

어딘가에 a를 다 뭉쳐놔야합니다. a를 뭉쳐놓을 위치 안에 있는 b를 밖에 있는 a와 교환해주면 됩니다. 즉 보고있는 위치 안의 b의 개수를 세는 것이 교환 최소 횟수가 됩니다. a를 뭉쳐놓을 수 있는 모든 위치에 대해 위 과정을 수행합니다.

abababababa : a가 총 6개

(ababab)ababa : 괄호 안에 a를 뭉쳐넣을것. 괄호의 길이 = 6. 괄호 안의 b를 밖으로 다 빼려면 3번 교환하면 됨.

a(bababa)baba : 이렇게 가능한 괄호 위치를 모두 탐색해주면 됩니다!

파이썬 음수 인덱스를 사용해서 고리형을 구현했습니다.

 

코드

import sys
def solution(input) :
    # a의 개수 - 가장 많이 연속된 a의 개수 XXX
    # a를 어디에 뭉쳐놓을거냐 -> 그 위치에 들어있는 b를 다 제거한다.
    # 위 과정을 슬라이딩 윈도우로 처리

    # 예외 케이스
    # aaaaaa 일때
    # a
    # b (?) or bbbb (?)


    L = input().strip()
    acnt = L.count('a')
    N = len(L)
    
    cntb = L[N-acnt:].count('b')
    mincnt = 9999999

    for e in range(N) : # e : 슬라이딩윈도우 마지막
        prev_s = L[e-acnt]
        new_e = L[e]
        if prev_s == 'b' : cntb-=1
        if new_e == 'b' : cntb+=1
        mincnt = min(mincnt,cntb)
    
    print(mincnt)

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac