[baekjoon] 백준 17615번(파이썬): 볼 모으기

문제

17615번: 볼 모으기

알고리즘

- 레드와 블루가 오른쪽과 왼쪽으로 모으는 경우를 생각해서 문제를 수행한다.

- 모을 때 뭉텅이가 생기는 경우는 이사 온 볼을 제외한 그다음 볼만으로 모으면 된다. 

=> 그다음 볼들이 있다면 그다음 볼들이 먼저 이동한 후에 첫 번째 볼이 이동하는 것이 최소 횟수이므로. 

코드

import sys


n = int(sys.stdin.readline())
m = list(map(str, sys.stdin.readline().strip()))
answer = []
blue = 0
red = 0
cnt = 0

# 우측으로 레드 보내기
for i in range(n):
    if m[i] == "R":
        red += 1

    if m[i] == "B" and red:
        cnt += red
        red = 0

answer.append(cnt)

# 우측으로 블루 보내기
cnt = 0
for i in range(n):
    if m[i] == "B":
        blue += 1

    if m[i] == "R" and blue:
        cnt += blue
        blue = 0

answer.append(cnt)

# 좌측으로 레드 보내기
m.reverse()
cnt = 0
red = 0
for i in range(n):
    if m[i] == "R":
        red += 1

    if m[i] == "B" and red:
        cnt += red
        red = 0

answer.append(cnt)


# 좌측으로 블루 보내기
blue = 0
cnt = 0
for i in range(n):
    if m[i] == "B":
        blue += 1

    if m[i] == "R" and blue:
        cnt += blue
        blue = 0

answer.append(cnt)
print(min(answer))

 

다른 사람 정답 코드(코드가 짧다..)

import sys

N = int(sys.stdin.readline().strip())
balls = str(sys.stdin.readline().strip())
cnt = []

# 우측으로 레드 모으기
rexplore = balls.rstrip('R')
cnt.append(rexplore.count('R'))

# 우측으로 블루 모으기
rexplore = balls.rstrip('B')
cnt.append(rexplore.count('B'))

# 좌측으로 레드 모으기
lexplore = balls.lstrip('R')
cnt.append(lexplore.count('R'))

# 좌측으로 블루 모으기
lexplore = balls.lstrip('B')
cnt.append(lexplore.count('B'))

print(min(cnt))

strip을 통해 오른쪽, 왼쪽에 있는 뭉텅이를 제외하고 각 볼의 색을 카운트한다.

각 볼의 색을 카운트하는 이유는 위에서 설명한 뭉텅이를 제외한 알고리즘과 똑같다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법