[BOJ/Python] 1522번: 문자열 교환

문제

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

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

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

 

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.

 

출력

첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.

 

첫 시도에는 순환구조이므로 aabbbaaaa 인 경우도 a가 모두 연속으로 인정되니까 배열의 첫과 끝부분에 연속인 a를 모두 제거하고 
남은 원소로만 교환개수를 세어서 진행 해보려고 했다. 

앞뒤 연속된 원소는 모두 제거하고 남은 배열에 존재하는 a의 개수를 세어서 저장하고 
b가 나올때마다 저장한 개수를 감소시키면서 개수가 0이면 멈추는 로직을 짰는데 사실 

모든 테이스 케이스랑 질문게시판에 올라온 테스트 케이스까지 통과 되었지만 2% 에서 얄짤없이 컷당했따..

 

아직까지 왜 틀렸는지에 대한 이유는 알수없다..

 

잘못된 코드

from collections import deque
import sys
import copy
input = sys.stdin.readline
str = deque(list(input().rstrip()))

def calculate(x, y, str):
  s, t = x, y
  arr = copy.deepcopy(str)
  while arr:
    if arr[0] == s:
      arr.popleft()
    else: break

  while arr:
    if arr[-1] == s:
      arr.pop()
    else: break

  print(s,str)

  a= arr.count(s)
  cnt1, cnt2, idx = 0, 0, 0

  while arr:
    if a <=0: break
    if arr[idx] == t: cnt1 += 1
    a -= 1
    idx += 1

  idx = len(arr) - 1
  a= arr.count(s)
  while arr:
    if a <=0: break
    if arr[idx] == t: cnt2 += 1
    a -= 1
    idx -= 1
  return min(cnt1,cnt2)

print(min(calculate('a','b',str),calculate('b','a',str)))

 

결국엔 알고리즘 분류 힌트를 보면서 슬라이딩 윈도우를 사용해야함을 알고 접근했다.

 

올바른 코드

import sys
input = sys.stdin.readline
input_str = input().rstrip()

#순환구조이기 때문에 2개로 이어주기
string = list(input_str + input_str)

a_cnt = input_str.count('a')
max_cnt, cnt = 0, 0

# 문자열 개수 + 총 a의 개수만큼 for 문 돌기
# 배열의 개수 + 슬라이딩 윈도우의 크기 만큼 반복
for i in range(len(input_str) + a_cnt):
	# 인덱스가 슬라이딩 윈도우의 크기보다 작을때는 초반 슬라이딩 윈도우의 개수를 세기위해 cnt++한다.
    if i < a_cnt:
        if string[i] == 'a':
          cnt += 1
    else: 
    # 인덱스가 슬랑이딩 윈도우의 크기를 넘어가면 'a' 들어오고 나감에 따라 증감시킨다.
        if string[i] == 'a':
            cnt += 1
        if string[i-a_cnt] == 'a':
            cnt -= 1
    # 최대값으로 저장한다.
    max_cnt = max(max_cnt,cnt)

# 최소교환횟수를 구해야하므로 총'a'의 개수에서 최대개수를 뺀다.
answer = a_cnt - max_cnt

print(answer)

 

순환구조이기 때문에 해당문자열을 2개로 붙여서 배열을 만들고
문자열에 존재하는 모든 'a'의 개수를 저장한다. 이 개수가 활용할 슬라이딩 윈도우의 크기가 된다. 

이유는 모든 'a'가 연속 이어야하기 때문에 이 슬라이딩 윈도우계속 한칸씩 옆으로 움직이면서 'a'의 개수가 가장 많을 때가

교환해야될 'a'의 개수가 가장 적은 경우가 된다. 따라서 이때의 'a'의 개수를 구해 총 'a' 의 개수에서 빼면 최소 교환 횟수를 구할 수 있다.