[백준] 17615번: 볼 모으기 풀이

사용한 기술 스택들:  

 

17615번: 볼 모으기 (acmicpc.net)

17615번: 볼 모으기

 

코드:

import sys

input = lambda: sys.stdin.readline().rstrip()
def move_balls(type_of_ball_to_move,s):
    s=s.lstrip(type_of_ball_to_move)
    return s.count(type_of_ball_to_move)

n = int(input())
s=input()
# To consider: red to left, red to right, blue to left, blue to right
print(min(
    move_balls("R",s),
    move_balls("R",s[::-1]),
    move_balls("B",s),
    move_balls("B",s[::-1])))

 

 

풀이:

 

이 문제에서는 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다.

 

즉, 나올 수 있는 결과는

1. 빨간색 공들이 왼쪽에 모이고 파란색 공들이 오른쪽에 모인다
2. 파란색 공들이 왼쪽에 모이고 빨간색 공들이 오른쪽에 모인다

여기서 1번을 만들기 위해서 본다면 움직일 수 있는 공의 색깔은 하나기 때문에 빨간색 공만 움직여서 1로 만들기와 파란색 공만 움직여서 1로 만들기가 있다.

 

그렇다면 총 이 문제에서 나올 수 있는 경우의 수는 4가지이다.

 

1. 빨간색만 옮겨서 빨간색 모임을 왼쪽으로
2. 빨간색만 옮겨서 빨간색 모임을 오른쪽으로
3. 파란색만 옮겨서 파란색 모임을 왼쪽으로
4. 파란색만 옮겨서 파란색 모임을 오른쪽으로

자 여기서 이 그림을 보자.

만약에 1번의 경우의 수를 수행하고 싶으면 3번 공과 5번 공을 움직이면 된다. 1번 공은 이미 그 위치에 있기 때문에 움직일 필요가 없다.

 

여기서 공의 움직이는 순서가 중요한데, 만약에 3번 공이 먼저 2번 파란 공을 뛰어넘고 5번 공이 나머지 두 개의 공을 뛰어넘게 되면 이동 횟수는 2가 된다.

 

하지만, 5번 공이 먼저 움직이게 되면, 5번 공은 4번 공만 뛰어넘을 수 있고 3번 공이 다시 움직인 후에야 5번 공을 한번 더 움직여 줘야 하기 때문에 이동 횟수는 3이 된다.

 

여기서 그리디한 방법으로 간단하게 생각하면 어떤 색깔의 공을 왼쪽으로 다 옮기고 싶으면 제일 왼쪽의 색깔 공부터 옮기는 게 최소 이동 횟수이다.(이래야지 같은 색깔의 공을 넘지 못해서 카운트가 하나 더 올라가는 것을 막을 수 있음).

 

즉, 이미 그 모임(왼쪽이나 오른쪽)에 이미 있는 색깔 공들 모임을 제외한 나머지의 같은 색깔 공들의 숫자가 이동 횟수가 된다.

 

그렇다면 위에서 말했던 4가지 경우의 수를 다 수행하고 이중에서의 이동 횟수의 최솟값이 답이 된다는 것을 알 수 있다.

 

def move_balls(type_of_ball_to_move,s):
    s=s.lstrip(type_of_ball_to_move)
    return s.count(type_of_ball_to_move)

이 함수는 type_of_ball_to_move라는 색깔을 가진 공들을 왼쪽으로 옮겨줬을 때 이동 횟수를 세어주는 역할을 한다.

 

lstrip이라는 함수를 사용하면 앞에 type_of_ball_to_move를 가진 연결된 같은 색깔들을 지워주기 때문에 이미 움직일 필요가 없는 공들을 제외해준다.

 

이제 남은 그 색깔을 가진 공들은 왼쪽에 있는 공부터 넘겨주면 공 하나당 1이라는 이동 횟수가 걸리기 때문에 그냥 type_of_ball_to_move 색깔을 가진 공의 개수가 이동 횟수가 된다.

 

# To consider: red to left, red to right, blue to left, blue to right
print(min(
    move_balls("R",s),
    move_balls("R",s[::-1]),
    move_balls("B",s),
    move_balls("B",s[::-1])))

 

그래서 4가지 경우의 수를 다 수행하기 위해 색깔을 다르게, 그리고 s의 순서를 반대로도 해주면(이렇게 하면 오른쪽에 공을 모으는 것과 같다) 답이 나오게 된다.

 

처음에는 직접 순회를 해서 구현을 했지만 이런 문자열 풀이가 더 빨라서 글을 써 보았다.

 

 

소스코드:

baekjoonProblems/볼_모으기.py at main · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답