[Brute Force - 순열] 부등호

예제 입력 1

2

< >

예제 출력 1

897

021

 

https://www.acmicpc.net/problem/2529

 

- 이 문제에서 k + 1 자리의 최대, 최소 정수를 출력해야하므로, 최소 정수의 경우는 0부터 k+1까지의 숫자만 사용하면 된다. 예를 들어, 0 < 2 > 1 과 4 < 9 > 7 은 같은 결과이기 때문에, 굳이 그 이상의 숫자를 활용할 필요가 없고 시간 복잡도도 줄일 수 있다. 

 

- 순서를 고려해야하므로, 순열을 사용하여 문제를 해결할 수 있다. STL을 사용하지 않는 경우,  배열의 인덱스만 순열으로 바꾸어 처리하고, 그 인덱스로 숫자를 만들어 문제를 해결했다.

 

- STL없이 next_permuation을 직접 구현해 문제를 해결할 경우, 조합 문제에 대해서 사용하면 까다로운듯...

 

k = 2인 경우 k+1개의 배열의 인덱스의 순열을 나열하면 아래와 같다.

 

012

021

102

120

201

210

 

#include <stdio.h>
#define MAX_COUNT (10)

int big[MAX_COUNT] = { 0, };
int small[MAX_COUNT] = { 0, };
int indexer[MAX_COUNT] = { 0, };
char operators[MAX_COUNT] = { 0, };
int K;

void swap(int* ar, int a, int b)
{
	int temp = ar[a];
	ar[a] = ar[b];
	ar[b] = temp;
}

bool next_permutation(int* a, int n)
{
	int i = n - 1;
	while ((i > 0) && (a[i - 1] > a[i])) i--;

	if (i <= 0) return false;

	int j = n - 1;
	while ((i <= j) && (a[i - 1] > a[j])) j--;

	swap(a, i - 1, j);

	j = n - 1;
	while (i < j)
	{
		swap(a, i, j);
		i++; j--;
	}

	return true;
}

bool check(int* data, int* indexer, char* operators, int operatorsCnt)
{
	for (int i = 0; i < operatorsCnt; i++)
	{
		if (operators[i] == '<') if (data[indexer[i]] > data[indexer[i+1]]) return false;
		if (operators[i] == '>') if (data[indexer[i]] < data[indexer[i+1]]) return false;
	}

	return true;
}

int main(void)
{
	scanf("%d", &K);

	for (int i = 0; i < K; i++)
	{
		while (true)
		{
			scanf("%c", &operators[i]);

			if (operators[i] != ' ' && operators[i] != '\n') break;
		}

		indexer[i] = i;
	}

	indexer[K] = K;
	K++;

	int startIdx = 9;
	for (int k = 0; k < K; k++)
	{
		small[k] = k;
		big[k] = startIdx--;
	}
		
	do
	{
		if (check(big, indexer, operators, K - 1))
		{
			for (int i = 0; i < K; i++) printf("%d", big[indexer[i]]);
			printf("\n");
			break;
		}
	} while (next_permutation(indexer, K));


	for (int i = 0; i < K; i++) indexer[i] = i;
	do
	{
		if (check(small, indexer, operators, K - 1))
		{
			for (int i = 0; i < K; i++) printf("%d", small[indexer[i]]);
			printf("\n");
			break;
		}
	} while (next_permutation(indexer, K));

	return 0;
}

 

[ 모범 답안(STL버전) ]

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

bool check(vector<int> perm, vector<char> a)
{
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] == '<' && perm[i] > perm[i + 1]) return false;
		if (a[i] == '>' && perm[i] < perm[i + 1]) return false;
	}

	return true;
}

int main(void)
{
	int k;
	scanf("%d", &k);

	vector<char> a(k);
	for (int i = 0; i < k; i++)
	{
		char input;

		while (true)
		{
			scanf("%c", &input);
			if (input != ' ' && input != '\n') break;
		}

		a[i] = input;
	}

	vector<int> small(k + 1);
	vector<int> big(k + 1);

	for (int i = 0; i <= k; i++)
	{
		small[i] = i;
		big[i] = 9 - i;
	}

	do
	{
		if (check(small, a)) break;
	} while (next_permutation(small.begin(), small.end()));

	do
	{
		if (check(big, a)) break;
	} while (prev_permutation(big.begin(), big.end()));

	for (int i = 0; i < big.size(); i++)
		printf("%d", big[i]);
	printf("\n");

	for (int i = 0; i < small.size(); i++)
		printf("%d", small[i]);
	printf("\n");

	return 0;
}

 

[ C# 6.0 ]

using System;
using System.Collections.Generic;

namespace Algorithm_Csharp6
{
    public class NumberArr
    {
        public List<int> arr = new List<int>();

        public NumberArr() { }

        public bool next_item(Func<int,int,bool> compareFunc)
        {
            int i = arr.Count - 1;
            while ((i > 0) && (compareFunc(arr[i - 1], arr[i]))) i--;

            if (i <= 0) return false;

            int j = arr.Count - 1;
            while ((i <= j) && (compareFunc(arr[i - 1], arr[j]))) j--;

            swap(i - 1, j);

            j = arr.Count - 1;
            while (i < j)
            {
                swap(i, j);
                i++;
                j--;
            }

            return true;
        }

        public bool check(List<char> operArr)
        {
            for(int i = 0; i < operArr.Count; i++)
            {
                if (operArr[i] == '>' && (arr[i] < arr[i + 1])) return false;
                if (operArr[i] == '<' && (arr[i] > arr[i + 1])) return false;
            }

            return true;
        }

        private void swap(int a, int b)
        {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            string input;
            List<char> operArr = new List<char>();

            NumberArr big = new NumberArr();
            NumberArr small = new NumberArr();

            int N;
            input = Console.ReadLine();
            Int32.TryParse(input, out N);

            input = Console.ReadLine();
            
            for(int i = 0; i < input.Length; i++)
            {
                if (input[i] != ' ' && input[i] != '\n')
                    operArr.Add(input[i]);
            }

            for(int i = 0; i < N+1; i++)
            {
                big.arr.Add(9 - i);
                small.arr.Add(i);
            }

            do
            {
                if (big.check(operArr)) break;
            } while (big.next_item((a,b) =>
                {
                    return a < b;
                }
            ));

            do
            {
                if (small.check(operArr)) break;
            } while (small.next_item((a, b) =>
            {
                return a > b;
            }
            ));

            for (int i = 0; i <= N; i++)
                Console.Write(big.arr[i]);
            Console.WriteLine();

            for (int i = 0; i <= N; i++)
                Console.Write(small.arr[i]);
            Console.WriteLine();
        }
    }
}