우선권을 가진 소들

면접 대비

시간 제한1초메모리 제한128 MB

요약

1, 2, 3으로 이루어진 수열이 주어질 때, 모든 1을 앞에, 그다음 2를, 마지막에 3을 모으기 위해 필요한 최소 교환 횟수를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 배열, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

$N$ 마리의 소가 있다 ( $1 \le N \le 1000$ ). 각 소는 우유 생산량에 따라 $1$ , $2$ , $3$ 중 하나의 우선권 번호를 부여받으며, 이 번호는 우물에서 물을 마시는 순서를 결정한다. 우선권 번호가 $1$ 인 소가 가장 먼저 마시고, $3$ 인 소가 가장 나중에 마신다.

소들은 어떤 순서로 한 줄로 서 있으며, 우선권 번호가 $1$ 인 소들이 모두 줄의 앞쪽에, $2$ 인 소들이 그 뒤에, $3$ 인 소들이 맨 뒤에 모이도록 다시 정렬해야 한다.

한 번의 교환은 줄에 있는 두 소의 위치를 서로 바꾸는 것이다. 소들을 올바르게 정렬하는 데 필요한 교환의 최소 횟수를 구하여라.

입력

첫째 줄: 정수 $N$
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에는 줄에서 $i$ 번째 위치에 있는 소의 우선권 번호가 하나씩 주어진다.

출력

첫째 줄: 소들을 올바르게 정렬하는 데 필요한 최소 교환 횟수를 나타내는 정수 하나

힌트

다음은 정렬하는 한 가지 방법이다 (< 표시는 교환에 참여하는 위치를 나타낸다):

2   2   2< 1   1
2< 1   1   1   1
1< 2   2   2   2
3   3< 2   2   2 
3   3   3   3< 2
3   3   3   3   3
2   2< 3   3   3
3   3   3   3   3
1   1   1< 2< 3

예제4

예제 1
입력
```
9
2
2
1
3
3
3
2
3
1
```
예상 출력
```
4
```
예제 2
입력
```
6
1
1
2
2
3
3
```
예상 출력
```
0
```
예제 3
입력
```
1
3
```
예상 출력
```
0
```
예제 4
입력
```
4
2
2
2
2
```
예상 출력
```
0
```