문제
빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.
바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.
예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.
<그림 1>
<그림 2>
<그림 3>
반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.
<그림 4>
일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.
입력
첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.
출력
최소 이동횟수를 출력한다.
풀이
그리디에는 익숙하지 않아서 빨간 공과 파란 공을 양쪽으로 모아버리는 아이디어까지는 떠올렸는데 구체적인 풀이가 잘 생각이 안났다. 찾아보니 좋은 풀이 방법이 있어서 따라 풀어봤다
네 가지 경우로 나누어서 생각해볼 수 있다
- 빨간 공만 움직여서 빨간 공을 왼쪽에 모으기
- 빨간 공만 움직여서 빨간 공을 오른쪽에 모으기
- 파란 공만 움직여서 파란 공을 왼쪽에 모으기
- 파란 공만 움직여서 파란 공을 오른쪽에 모으기
움직여야하는 이동 횟수는 목표로하는 색의 맨 끝에 위치한 공을 제외한 동일한 색의 나머지 공의 개수이다
예를 들어, 빨간 공만 움직여서 빨간 공을 왼쪽에 모으고 싶다면
RBBBRBRRR의 예시에서 맨 왼쪽의 R을 제외한 나머지 R 4개가 왼쪽으로 이동해야한다
이동할 때 가장 왼쪽에 있는 공부터 이동해야 최소 횟수로 이동할 수 있다
중간이나 끝의 공이 먼저 이동하게 되면 이동 횟수가 늘어나게 된다
파이썬의 lstrip 함수를 사용해서 맨 왼쪽의 목표 공들을 제거한 후에 개수를 세어준다
오른쪽에 모으는 경우는 문자열을 뒤집어서 수행하면 동일한 결과를 낸다
코드
import sys
n = int(sys.stdin.readline())
arr = sys.stdin.readline().strip()
def move_balls(ball,s):
s=s.lstrip(ball)
return s.count(ball)
print(min(
move_balls("R",arr),
move_balls("R",arr[::-1]),
move_balls("B",arr),
move_balls("B",arr[::-1])))