[ BOJ ] 17615 : 볼 모으기 ( SILVER 1 ) / Python

문제 링크 : https://www.acmicpc.net/problem/17615

17615번: 볼 모으기

 

문제

빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.

1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

입력

첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.

출력

최소 이동횟수를 출력한다.

풀이 과정

고려해야 하는 경우는 4가지이다.

1. 빨간색 볼을 앞으로 옮기기 - 필요한 이동횟수는 빨간색 볼의 개수 - 맨 앞에 위치한 빨간색 볼 그룹의 개수

2. 빨간색 볼을 뒤로 옮기기 - 필요한 이동횟수는 빨간색 볼의 개수 - 맨 뒤에 위치한 빨간색 볼 그룹의 개수

3. 파란색 볼을 앞으로 옮기기 - 필요한 이동횟수는 파란색 볼의 개수 - 맨 앞에 위치한 파란색 볼 그룹의 개수

4. 파란색 볼을 뒤로 옮기기  - 필요한 이동횟수는 파란색 볼의 개수 - 맨 뒤에 위치한 파란색 볼 그룹의 개수

 

빨간색 볼 - 파란색 볼 문자열을 색깔마다 그룹으로 묶어, 맨 앞과 맨 뒤에 위치한 볼 그룹을 찾아서 쉽게 풀이했다.

 

 

import sys
input = sys.stdin.readline

n = int(input().rstrip())
string = input().rstrip()
group = []

now_col = 'A'
now_cnt = 0
for i in range(n):
    if now_col != string[i]:
        if i != 0:
            group.append([now_col, now_cnt])
        now_col = string[i]
        now_cnt = 1
    else:
        now_cnt += 1

group.append([now_col, now_cnt])

# 빨간색 옮기기 - 앞으로
res = string.count('R')
if group[0][0] == 'R':
    res -= group[0][1]

# 빨간색 옮기기 - 뒤로
now = string.count('R')
if group[-1][0] == 'R':
    now -= group[-1][1]
res = min(res, now)

# 파란색 옮기기 - 앞으로
now = string.count('B')
if group[0][0] == 'B':
    now -= group[0][1]
res = min(res, now)

# 파란색 옮기기 - 뒤로
now = string.count('B')
if group[-1][0] == 'B':
    now -= group[-1][1]
res = min(res, now)

print(res)