[백준] 17615 볼 모으기

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

---

문제 요약

볼의 종류는 R, B 두가지로 볼이 주어졌을 때 모두 한 뭉텅이씩 묶도록 해야한다.
이때 제일 처음 움직인 볼이 R이라면 다음 볼도 무조건 R만 움직일 수 있고 B를 움직였다면 B만 움직어야 한다.

이러한 경우를 만들 수 있는 최소 횟수를 구하는 문제이다.

---

나의 접근 방식

처음에 각 볼의 갯수를 각각 구하고
자료구조 Stack을 이용하여 문자열을 R,B 두가지 기준으로 나눠서 한 종류의 볼이 모두 들어올 때 나머지 종류의 볼의 갯수를 움직인 횟수라고 접근하여 문제를 풀었다.

from collections import deque

n = int(input())

S = input()

dq = deque(S)

R = S.count('R')
B = S.count('B')

ans = 1e9

R_count = 0
B_count = 0

while R_count < R and dq:
    element = dq.popleft()

    if element == 'B':
        B_count += 1
    else :
        R_count += 1
ans = min(ans, min(R_count, B_count))


R_count = 0
B_count = 0
dq = deque(S)

while B_count < B and dq:
    element = dq.popleft()

    if element == 'B':
        B_count += 1
    else:
        R_count += 1
ans = min(ans, min(R_count, B_count))

print(ans)

이러한 방식으로 풀었을 때 15%에서 틀렸다.

다른 사람 풀이

https://fre2-dom.tistory.com/m/427 블로그를 참조했습니다!

좌측과 우측을 기준으로 한쪽으로 몰려있는 볼을 제거하고 제거한 볼에 대한 종류의 갯수를 모두 한쪽으로 옮겨주는 방식의 논리를 사용했다.

우측으로 레드 모으기 -> 우측에 모인 R은 이미 정렬되어있으므로 제거 후 나머지 배열에 존재하는 R구슬을 모두 우측으로 몰아주기만 하면 된다.

이때 rstrip,lstrip을 사용했었는데 생각지도 못한 참신한 방법이었다.

n = int(input())
balls = input()

cnt = []

# 우측으로 레드 모으기
# 우측에 모인 R은 이미 정렬되어 있으므로 남은 R만 오른쪽으로 모으면 됨.

cnt.append(balls.rstrip('R').count('R'))
cnt.append(balls.rstrip('B').count('B'))
cnt.append(balls.lstrip('R').count('R'))
cnt.append(balls.lstrip('B').count('B'))

print(min(cnt))