해당 게시글에서는 [백준] 1522 문자열 교환 문제를 해설하고 Python을 이용하여 풀고자 한다.
💡 문제 풀이
1522번 문제는 투 포인터에 대한 문제로 두 개의 포인터를 조절하여 두 포인터가 가리키는 값이 특정한 조건을 만족하도록 하는 방식의 알고리즘이다. 투 포인터 알고리즘 중에서도 두 포인터를 일정한 간격으로 이동하는 슬라이딩 윈도우 알고리즘에 해당한다. 슬라이딩 윈도우인 이유는 아래 문제 해설에서 설명하겠다.
이 문제에서 구하고자 하는 값은 a와 b로만 이루어진 문자열에 대해 a를 모두 연속으로 만들기 위한 최소 교환 횟수이다.
예시를 통해 풀이 방법을 설명하기 전에 다음을 이해하자!
1️⃣ 교환 후 연속된 a 문자열의 길이는 입력된 문자열 속 a의 개수와 같다.
2️⃣ 즉, a의 개수와 동일한 길이로 연속된 문자열을 슬라이싱 하고 슬라이싱한 문자열 내부에 있는 b와 외부에 있는 a와 교환하면 a가 연속되게 된다. 이때 교환 횟수는 슬라이싱한 문자열 내부에 있는 b의 개수와 동일하다.
🔎 예제
만약 abababababababa가 입력으로 주어졌다고 하자. 포인터는 문자열의 0번째 인덱스에 위치한 a에서부터 시작한다. 입력된 문자열에서의 a의 개수는 8개이다. 즉 최종적으로 교환이 일어난 후의 a가 연속된 문자열의 길이는 8이라는 것이다. 그럼 0번째 인덱스부터 8개를 슬라이싱 하면 다음과 같이 된다.
✔ (abababab)abababa
() 안에 있는 값이 슬라이싱한 문자열이며, () 내부에 있는 부분을 모두 a로 연속되게 만들고 싶은 것이다. 그러기 위해선 () 내부의 b의 값을 () 외부의 a값과 교환하면 된다. 그렇다면 교환 횟수는 b의 개수가 되며 해당 예제에서는 4가 된다.
✔ a(babababa)bababa
인덱스를 한 칸 더 옮겨 봐보자. 아까 설명했던 것과 같이 () 안에 있는 b의 값을 외부의 a값과 교환해줘야 하므로 해당 예제에서의 교환 횟수는 4가 된다.
이와 같이 입력된 문자열을 슬라이싱 할 수 있는 부분에 대해 모두 a의 개수와 동일한 길이로 슬라이싱 하여 모든 경우에 대해 교환 횟수(슬라이싱한 문자열 내부의 b의 개수)를 구한 후 최솟값을 구하면 된다. 이때 동일한 길이로 계속해서 슬라이싱 하기 때문에 슬라이딩 윈도우에 해당하는 문제인 것이다.
다음은 for문을 이용해 시작 포인터(i) 위치 부터 동일한 길이(a의 개수)로 슬라이싱하여 b의 개수를 세고 모든 경우에 대해 값을 구하여 그 중 최소값을 구하는 코드다.
1
2
for i in range(len(s)-(a-1)):
min_val = min(min_val, s[i:i+a].count('b'))
📌 주의사항
문제의 조건에 원형 문자열이라는 조건이 있다. 이는 다음과 같이 슬라이싱이 가능하다는 것이다.
✔ ababab)abababa(ba
따라서 이를 처리 하기 위해 코드에서 문자열을 다음 코드와 같이 늘려주었다. 그냥 동일한 s를 더해줘도 되지만 필요 없는 부분까지 더해줄 필요가 없으므로 s[0:a-1]과 같은 문자열을 더해주었다.
1
s += s[0:a-1] # 원형 문자열
for문의 range가 len(s)-(a-1)까지 인 것도 원형 문자열을 처리하면서 기존에 입력된 문자열의 길이가 변형되어서 따로 처리를 해준 것이다.
📂 코드
1
2
3
4
5
6
7
8
s = input() # 문자열 입력
a = s.count('a') # 입력된 str에서의 a의 개수
s += s[0:a-1] # 원형 문자열 처리
min_val = float('inf') # 최솟값
for i in range(len(s)-(a-1)):
min_val = min(min_val, s[i:i+a].count('b'))
print(min_val)