서론
그리디 문제입니다.
다른 분의 풀이를 참고하였습니다.
난이도
실버 1
문제
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초(추가 시간 없음) | 512MB |
빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.
- 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
- 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.
예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.
<그림 1>
<그림 2>
<그림 3>
반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.
<그림 4>
일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.
입력
첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.
출력
최소 이동횟수를 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | N ≤ 10 |
| 2 | 22 | N ≤ 1,000 |
| 3 | 14 | N ≤ 500,000, 처음 상태에서 모든 파란 공은 연속해서 존재한다. |
| 4 | 49 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예시
예제 입력 1
9
RBBBRBRRR예제 출력 1
2예제 입력 2
8
BBRBBBBR예제 출력 2
1풀이
각 공을 한쪽으로 모는 모든 경우의 수 중 작은 값을 출력합니다.
총 경우의 수는 네 가지 입니다.
- 빨간 공을 오른쪽으로 옮기는 경우
- 파란 공을 오른쪽으로 옮기는 경우
- 빨간 공을 왼쪽으로 옮기는 경우
- 파란 공을 왼쪽으로 옮기는 경우
이 네 가지 경우 중 가장 작은 값을 출력합니다.
move()에서 rstrip()과 lstrip()을 쓰는 이유는 한 쪽으로 공을 옮길 때, 이동하는 쪽의 이미 몰려 있는 공들을 없애고 나머지를 이동해야 하기 때문입니다.
이동하는 쪽의 특정 색의 공들을 없애면 남겨진 특정 색의 공들만 옮기면 되기 때문에 그 공들만 개수를 세어주면 되는 겁니다.
e.g)
예제 1번 예시
입력 = RBBBRBRRR
ans = []
move(True, 'R') -> 빨간 공의 오른쪽을 제거 후 남은 공들을 오른쪽으로 옮겨야 하는 경우
tmp = ball.rstrip('R') = RBBBRB, tmp.count('R') = 2
ans = [2]
move(True, 'B') -> 파란 공의 오른쪽을 제거 후 남은 공들을 오른쪽으로 옮겨야 하는 경우
tmp = ball.rstrip('B') = RBBBRBRRR, tmp.count('B') = 4
ans = [2, 4]
move(False, 'R') -> 빨간 공의 왼쪽을 제거 후 남은 공들을 왼쪽으로 옮겨야 하는 경우
tmp = ball.lstrip('R') = BBBRBRRR, tmp.count('R') = 4
ans = [2, 4, 4]
move(False, 'B') -> 파란 공의 왼쪽을 제거 후 남은 공들을 왼쪽으로 옮겨야 하는 경우
tmp = ball.lstrip('B') = RBBBRBRRR, tmp.count('B') = 4
ans = [2, 4 ,4, 4]
따라서 정답은 min(ans)인 2가 출력됩니다.
코드
def move(right, color): # 공 이동, right = 오른쪽인지 여부, color = 옮기는 공의 색
# 오른쪽 방향(right = True)이면 매개변수로 들어온 색(color)의 오른쪽 공들을 제거
# 왼쪽 방향(right = False)이면 매개변수로 들어온 색(color)의 왼쪽 공들을 제거
tmp = ball.rstrip(color) if right else ball.lstrip(color)
# 한쪽 끝의 공들 제거 후 남은 공들의 특정 색의 공 개수를 카운트하여 ans에 추가
ans.append(tmp.count(color))
n = int(input())
ball = input()
ans = []
move(True, 'R') # 빨간 공을 오른쪽으로 옮김
move(True, 'B') # 파란 공을 오른쪽으로 옮김
move(False, 'R') # 빨간 공을 왼쪽으로 옮김
move(False, 'B') # 파란 공을 왼쪽으로 옮김
print(min(ans)) # 네 경우의 수 중 가장 작은 값 출력실행 결과
