[백준] 17615번 볼 모으기 (Python)

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

📌 문제

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

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

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.

반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.

 

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.

 

📌 입력

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

 

 

📌 출력

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

---

📌 풀이 방식 

볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 해야 합니다. 

같은 색 볼끼리 인접하게 놓기만 하면 되기 때문에 

1. 볼을 앞으로 옮기는 경우 

2. 볼을 뒤로 옮기는 경우

총 두 가지의 경우로 옮길 수 있는데요. 

 

<- 앞으로 옮기는 경우 가장 왼쪽

-> 뒤로 옮기는 경우 가장 오른쪽의 

볼의 색과 인접되어 있는 개수만큼은 옮기지 않아도 되기 때문에

옮기지 않는 개수를 총 개수에서 빼주고 어떤 경우가 가장 적은 볼을 옮기면 되는지 계산해주면 됩니다 !!

 

정리해보자면 총 8가지의 경우를 계산 후 가장 적게 옮기면 되는 볼의 개수를 출력하면 됩니다. 

[볼을 앞으로 옮기는 경우] 

가장 왼쪽 볼이 파란색일 때

1. 총 파란색 볼 - 맨 왼쪽에 인접해 있는 파란색 볼의 개수 

2. 총 빨간색 볼

 

가장 왼쪽 볼이 빨간색일 때

3. 총 파란색 볼 

4. 총 빨간색 볼 - 가장 왼쪽에 인접해 있는 빨간색 볼의 개수

 

[볼을 뒤로 옮기는 경우]

가장 오른쪽 볼이 파란색일 때

5. 총 파란색 볼 - 가장 오른쪽에 인접해 있는 파란색 볼의 개수 

6. 총 빨간색 볼

 

가장 오른쪽 볼이 빨간색일 때

7. 총 파란색 볼 

8. 총 빨간색 볼 - 가장 오른쪽에 인접해 있는 빨간색 볼의 개수

 

이렇게 하면 되겠다라고 생각했는데, 그냥 반복문을 사용해서 풀다보니 정답은 맞았지만 시간이 244 ms 가 나오더라구요 ,, 

그래서 어떻게하면 시간과 코드길이를 줄일 수 있을까 생각하다가

count 와 find 그리고 min 을 사용하면 되겠다라고 생각했습니다. 

 

count 를 통해 총 B 와 R 의 개수를 세주고, 

find, rfind 를 통해 인접한 볼의 개수를 세줍니다. (맨 앞의 볼이 B 라면 R 이 가장 처음 나오는 위치를 계산해서 인접해 있는 B 의 개수를 구하는 방식)

그리고 min 을 통해 가장 최소 이동횟수를 구해줬습니다 :)

 

결과를 224ms -> 40 ms 로 줄이고, 코드도 훨씬 깨끗해졌습니다 !!!

---

📌 코드

N = int(input())
ball = input()

# 총 B 와 R 의 개수를 세준다.
blue = ball.count('B')
red = ball.count('R')

# 맨 앞의 인접한 볼의 개수를 세서
# 총 개수에서 빼주고 어떤 값이 더 작은지 저장해준다.
first = ball[0]
red_minus = ball.find('B') if first == 'R' else 0
blue_minus = ball.find('R') if first == 'B' else 0
first_result = min(blue - blue_minus, red - red_minus)

# 맨 뒤의 인접한 볼의 개수를 세서
# 총 개수에서 빼주고 어떤 값이 더 작은지 저장해준다.
last = ball[-1]
red_minus = len(ball) - ball.rfind('B') - 1 if last == 'R' else 0
blue_minus = len(ball) - ball.rfind('R') - 1 if last == 'B' else 0
last_result = min(blue - blue_minus, red - red_minus)

# 맨 앞의 결과값과 맨 뒤의 결과값 중 더 적은 값을 출력한다.
print(min(first_result, last_result))