첫 시도
- N이 5 * 10^5이므로 완전탐색으로는 해결 x
- 목표는 같은 색깔의 볼끼리 인접하도록 만드는 것, 볼을 이동시킬 때 그 사이에 몇개의 공이 있던 상관 x
- 고려해야 하는 경우의 수는 왼쪽에 빨간 공만 모을 경우, 파란 공만 모을 경우, 오른쪽에 빨간 공만 모을 경우, 파란 공만 모을 경우, 총 4가지만 고려하면 된다.
- 다만 숫자를 세기 시작하는 인덱스를 정하기 어려움 -> 구현 실패
해결
- 빨간 공과 파란 공 각각의 갯수를 구한다.
- 한 쪽에 모을 공의 색을 정하고 정한 방향의 시작점부터 다른 색의 공이 나올때까지 이동 -> 다른 색의 공이 나온다면 선택한 색깔의 전체 갯수와 지금까지 센 공의 갯수를 뺀다 -> 나온 결과가 이동해야 하는 횟수
- 예를들어 왼쪽에 빨간 공을 모을 것이고 공의 배치는 RBBBRBRRR 라면 전체 R의 갯수는 5개, 왼쪽부터 B를 만날때까지의 R의 갯수는 1이다. 여기서 이후의 모든 R을 왼쪽으로 옮기려면 총 4번의 이동이 있어야 한다. 이를 쉽게 계산할 수 있는 방법이 전체 R의 갯수에서 B를 만나기 전까지의 R의 갯수를 빼는 것이므로 5 - 1 = 4를 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
String[] input = br.readLine().split("");
int min = Integer.MAX_VALUE;
int red = 0;
int blue = 0;
for(int i = 0; i < input.length; i++){ // 빨간 공, 파란 공 숫자 count
if(input[i].equals("R")) red++;
else blue++;
}
String color = "R";
for(int i = 0; i < 4; i++){
int count = 0;
if(i<2) {
for (int j = 0; j < input.length; j++) {
if (input[j].equals(color)) {
count++;
} else {
break;
}
}
if (color.equals("R")) min = Math.min(min, red - count);
else min = Math.min(min, blue - count);
color = "B";
}
else{
for (int j = input.length -1; j >= 0; j--) {
if (input[j].equals(color)) {
count++;
} else {
break;
}
}
if (color.equals("R")) min = Math.min(min, red - count);
else min = Math.min(min, blue - count);
color = "R";
}
}
System.out.println(min);
}
}