문제

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

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

2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.
   예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.
   <그림1>
   
   <그림2>
   
   <그림3>
   

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

<그림4>

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

---

입력

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

---

출력

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

---

풀이

접근방법

시간제한 1초, 메모리512MB, N 이 (1 ≤ N ≤ 500,000)이다.
메모리가 넉넉하므로 메모리를 잘 쓰자 라는 생각을 가지고 문제에 임한다.

문제를 해결하기 위해서 발생하는 4가지 경우를 생각해본다.
1. 빨간색 공을 모두 왼쪽으로 이동
2. 빨간색 공을 모두 오른쪽으로 이동
3. 파란색 공을 모두 왼쪽으로 이동
4. 파란색 공을 모두 오른쪽으로 이동

빨간색 공을 모두 왼쪽으로 이동하는 것과 파란색 공을 모두 오른쪽으로 이동하는 것은 최종적으로 모양은 같지만 이동 횟수는 차이가 있다는 점에 주의하자

케이스1 을 예시로 보자
기존 배열에서 가장 왼쪽에 있는 빨간공을 왼쪽으로 이동시킨다.

• 왼쪽에 파란색공이 없다면 이미 가장 왼쪽이다.
• 왼쪽에 파란색공이 있다면, 파란공 무더기를 뛰어 넘어야 하므로 카운트를 증가시킨다.
  ( 가장 왼쪽의 빨간공을 기준으로 생각하므로, 왼쪽에는 파란색공 무더기가 존재하거나 없거나 반드시 둘 중 하나이다.)

다음 빨간색 공(기존의 두번째 빨간공)을 생각해보자.
첫번째 빨간색공이 가장 왼쪽으로 이동을 이미 완료하였으므로,
현재 공 역시 왼쪽에 파란색 공 무더기가 있거나, 존재하지 않거나 둘 중 하나이다.

(인덱스를 통해서 왼쪽에 파란색 공이 있는지를 확인할 수 있다.)

위와 같은 방식으로 4가지 케이스에 대해 모두 계산한 후, 최소값이 정답이 된다. 시간 복잡도O(N)

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	static int N;
	static String ballString;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());
		ballString = in.readLine();

		int minMoveCount = Integer.MAX_VALUE;
		// Case1. Red를 모두 왼쪽으로
		minMoveCount = Math.min(minMoveCount, getCountForLeft('R'));

		// Case2. Red를 모두 오른쪽으로
		minMoveCount = Math.min(minMoveCount, getCountForRight('R'));

		// Case3. Blue를 모두 왼쪽으로
		minMoveCount = Math.min(minMoveCount, getCountForLeft('B'));

		// Case4. Blue를 모두 오른쪽으로
		minMoveCount = Math.min(minMoveCount, getCountForRight('B'));

		System.out.println(minMoveCount);
	}

	private static int getCountForLeft(char type) {
		int result = 0;
		List<Integer> targets = new ArrayList<>();
		int firstOtherIndex = Integer.MAX_VALUE;
		boolean isFindFirst = false;

		for (int i = 0; i < N; ++i) {
			if (ballString.charAt(i) == type) {
				targets.add(i);
			} else {
				if (!isFindFirst) {
					isFindFirst = true;
					firstOtherIndex = i;
				}
			}
		}

		for (int i = 0; i < targets.size(); ++i) {
			if (firstOtherIndex < targets.get(i))
				result++;
		}
		return result;
	}

	private static int getCountForRight(char type) {
		int result = 0;
		List<Integer> targets = new ArrayList<>();
		int lastOtherIndex = Integer.MIN_VALUE;

		for (int i = 0; i < N; ++i) {
			if (ballString.charAt(i) == type)
				targets.add(i);
			else
				lastOtherIndex = i;

		}

		for (int i = 0; i < targets.size(); ++i) {
			if (lastOtherIndex > targets.get(i))
				result++;
		}
		return result;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}