USACO 2.1 - Sorting a Three-Valued Sequence

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.

PROGRAM NAME: sort3

INPUT FORMAT

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}

SAMPLE INPUT (file sort3.in)

9
2
2
1
3
3
3
2
3
1

OUTPUT FORMAT

A single line containing the number of exchanges required

SAMPLE OUTPUT (file sort3.out)

4

출처: http://train.usaco.org/

N 개의 1,2,3 중에 하나로 구성된 숫자가 주어진다고 할 때, N 개의 숫자를 오름차순으로 정렬하려 한다. 이때 두 개의 숫자를 swapping 하는 방법으로 정렬을 하려할 때 최소 swapping 횟수를 구하시오.

우선 주어진 숫자가 1,2,3 중에 하나이기 때문에 각 숫자의 정렬된 배열의 위치를 알 수 있습니다. 1의 경우 0 ~ [1의 개수 - 1], 2의 경우 [1의 개수] ~ [1과 2의 개수 -1] 이 됩니다. 그리고 최소 횟수를 구해야 되기 때문에 되도록이면 한 번의 swapping 으로 두 수 모두 제자리를 찾는 방법을 먼저 시도하면 최소 횟수를 구할 수 있습니다. 다만 코드가 지저분한 것이 걸리네요. 다시 정리할 필요가 있을 것 같습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
 
int n;
vector<int> numbers;
int eachNumbers[3];
 
int solve()
{
    int ret = 0;
 
    for (int i = 0; i < eachNumbers[0]; i++)
    {
        if (numbers[i] == 1)
            continue;
 
        int start, end;
 
        if (numbers[i] == 2)
        {
            start = eachNumbers[0];
            end = eachNumbers[0] + eachNumbers[1];
        }
        else
        {
            start = eachNumbers[0] + eachNumbers[1];
            end = n;
        }
 
        for (int j = start; j < end; j++)
        {
            if (numbers[j] == 1)
            {
                numbers[j] = numbers[i];
                numbers[i] = 1;
                ret++;
                break;
            }
        }
 
        if (numbers[i] == 1)
            continue;
        if (numbers[i] == 2)
        {
            start = eachNumbers[0] + eachNumbers[1];
            end = n;
        }
        else
        {
            start = eachNumbers[0];
            end = eachNumbers[0] + eachNumbers[1];
        }
 
        for (int j = start; j < end; j++)
        {
            if (numbers[j] == 1)
            {
                numbers[j] = numbers[i];
                numbers[i] = 1;
                ret++;
                break;
            }
        }
    }
 
    for (int i = eachNumbers[0]; i < eachNumbers[0] + eachNumbers[1]; i++)
    {
        if (numbers[i] == 3)
            ret++;
    }
 
    return ret;
}
 
int main()
{
    ifstream fin("sort3.in");
    ofstream fout("sort3.out");
 
    fin >> n;
 
 
    for (int i = 0; i < n; i++)
    {
        int num;
        fin >> num;
        numbers.push_back(num);
        eachNumbers[num - 1]++;
    }
 
    fout << solve() << endl;
 
    fin.close();
    fout.close();
    return 0;
}