[Python][백준] 1927. 문자열 교환

링크🔗

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

---

🗒️파이썬 코드 풀이

lst = list(input())
a_cnt = lst.count("a")
circle_lst = lst + lst

mn = 10000
for i in range(len(lst)):
    tmp_lst = circle_lst[i : i + a_cnt]
    mn = min(mn, tmp_lst.count("b"))
print(mn)

 

1. 브루트포스로 하나 하나 다 확인을 하는데, 슬라이딩 윈도우 방식을 쓰면 편하다. 

 

2. 문제의 문자열은 원형의 특성을 가지고 있기 때문에, lst + lst로 하여 연결시켰다.

(브루트포스로 확인 할 때는 기존 lst에 있는 것만 확인하면 된다.)

 

3. 교환을 하더라도 a의 개수는 정해저 있기 때문에,

a의 개수만큼 슬라이딩 윈도우를 하면서 그때 b 개수의 최소값을 구하면 된다

ex) abab
1. 해당 리스트에서 a의 개수는 2이다.
2. 먼저 abab + abab 를 해줘서 abababab를 만들어준다.
3. 4회(lst의 수만큼) 반복문을 돌려준다. (브루트포스)
4. 2 (a의 개수만큼) 슬라이딩 윈도우 

(1) [ab] ababab : b의 개수 1개

(2) a [ba] babab : b의 개수 1개

(3) ab [ab] abab : b의 개수 1개

(4) aba[ba] bab : b의 개수 1개

5. 교환 회수의 최소값은 1이 된다.

 

 

 

📌  문제 코멘트

교환이라는 말을 잘 해석해야한다.

나는 b를 a로 바꿔도 된다고 생각했다  (abba이면 abaa 이런식으로 ...)
여기서 말하는 교환은 (내부)위치의 교환이다.  (외부가 아니라 !!)

 

나만 그런건가 ...?  아무튼 이것만 잘 하면 구현이 어려운 문제는 아니다 !

 

 

📚문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

abababababababa

예제 출력 1 복사

3

예제 입력 2 복사

ba

예제 출력 2 복사

0

예제 입력 3 복사

aaaabbbbba

예제 출력 3 복사

0

예제 입력 4 복사

abab

예제 출력 4 복사

1

예제 입력 5 복사

aabbaaabaaba

예제 출력 5 복사

2

예제 입력 6 복사

aaaa

예제 출력 6 복사

0