백준_17615_볼 모으기

볼 모으기

문제

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

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

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

<그림 1> <그림 2> <그림 3>

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

<그림 4>

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

입력

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

출력

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

예제 입력 1

9
RBBBRBRRR

예제 출력 1

2

풀이 및 해설

출력값: 종류가 같은 볼끼리 위치하도록 옮길 때 볼을 이동하는 최소 횟수 구하기
[볼 옮기는 규칙]

• 한 번 선택한 종류만 옮길 수 있음
• 바로 옆에 다른 종류가 존재하면 한 번에 뛰어 넘음

그리디 알고리즘 이용

• 종류가 같은 볼끼리 배치하는 방법이 총 4가지
  1. 빨간 공(R)을 왼쪽으로 이동시키기
  2. 빨간 공(R)을 오른쪽으로 이동시키기
  3. 파란 공(B)을 왼쪽으로 이동시키기
  4. 파란 공(B)을 오른쪽으로 이동시키기
• 이때, [기준이 되는 공과 어느 방향으로 이동]시키는지에 따라 가장 가까운 위치에 배치되어 있는 공 이동시키기
  ex) 빨간 공(R)을 왼쪽으로 이동시키는 경우(RBBBRBRRR → RRRRRBBBB)
  • RBBBRBRRR 에서 해당 공을 먼저 이동 시키면 2번 이동시켜야 함
  • 따라서 가장 왼쪽에 배치되어 있는 빨간 공부터 이동시키면 됨

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 볼의 총 개수
const balls = input[1].split(''); // 초기 볼 배치 상태

let result = Number.MAX_SAFE_INTEGER;

const moveLeft = (color) => {
  let anotherCnt = 0;
  let cnt = 0;
  // 해당 공을 왼쪽으로 이동시키기
  for (let b = 0; b < N; b++) {
    if (anotherCnt !== 0 && balls[b] === color) cnt += 1; // 다른 종류 공이 있는 경우 공 옮기기
    if (balls[b] !== color) anotherCnt++; // 타겟의 다른 종류 공 카운트 증가(뛰어 넘어야 하는 공 개수)
  }
  return cnt;
};
const moveRight = (color) => {
  let anotherCnt = 0;
  let cnt = 0;
  // 해당 공을 오른쪽으로 이동시키기
  for (let b = N - 1; b >= 0; b--) {
    if (anotherCnt !== 0 && balls[b] === color) cnt += 1;
    if (balls[b] !== color) anotherCnt++;
  }
  return cnt;
};

result = Math.min(result, moveLeft('R')); // 1. 빨간 공(R)을 왼쪽으로 이동시키기
result = Math.min(result, moveRight('R')); // 2. 빨간 공(R)을 오른쪽으로 이동시키기
result = Math.min(result, moveLeft('B')); // 3. 파란 공(B)을 왼쪽으로 이동시키기
result = Math.min(result, moveRight('B')); // 4. 파란 공(R)을 오른쪽으로 이동시키기

console.log(result);