Problem 2.1.5 Sorting A Three-Valued Sequence

출처: https://train.usaco.org/usacogate

---

문제 설명

Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

입력

Line 1: N (1 <= N <= 1000), the number of records to be sorted
Lines 2-N+1: A single integer from the set {1, 2, 3}

출력

A single line containing the number of exchanges required

입력 예

9 
2 
2 
1 
3 
3 
3 
2 
3 
1

출력 예

4 

---

문제 풀이

정렬할 입력을 저장하면서, 1, 2, 3 숫자를 기록한다. bubble sort와 비슷한 방법으로 진행한다. 2보다 뒤쪽에 있는 1들을 2와 바꾼다. 3보다 뒤에 있는 1들을 3과 바꾼다. 마지막으로 3보다 뒤에 있는 2들을 3과 바꾼다. 

프로그램 내용

#define MAX_N 1000

int main()
{
    int N;
    fin >> N;

    vector <int> in_Nums;
    int eachNum[3] = {0};

    for (int idx=0; idx< N ; ++idx)
        fin >> num;
        in_Nums.push_back(num);
        eachNum[num-1]++;		/// count 1, 2, 3

    /// exchange 1 with 2 until eachNum[0] 
    /// part(eachNum[0], 1 , 2, N)
    int cnt=0;
    for(int i= eachNum[0]; i< N; ++i)
        if(in_Nums[i] == 1)
        for(int j=0;j<eachNum[0];++j)
            if(in_Nums[j] == 2)
                swap(in_Nums[i],in_Nums[j]);

    /// exchange 1 with 3 until eachNum[0]
    for(int i= eachNum[0]; i< N; ++i)
        if(in_Nums[i]== 1)
        for(int j=0;j<eachNum[0];++j)
            if(in_Nums[j]==3)
                swap(in_Nums[i],in_Nums[j]);

    /// exchange 2 with 3 eachNum[0]+eachNum[1]
    for(int i= eachNum[0]+eachNum[1]; i< N; ++i)
        if(in_Nums[i]== 2)
        for(int j=0;j<eachNum[0]+eachNum[1];++j)
            if(in_Nums[j]==3)
                swap(in_Nums[i],in_Nums[j]);

 

Chapter 2. Bigger Challenges