[BOJ] 백준 2529번 부등호 C++

문제

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

2529번: 부등호

백트래킹을 통해 순열을 구하는 문제이다. 연산자 끼워넣기 문제를 풀어봤다면 쉽게 풀 수 있었을 것이다.

필자는 문자열 -> 숫자로 변환하여 대소관계를 비교하려 하였는데 이 부분에서 시간을 많이 잡아먹었다. 그렇게 레퍼런스를 찾아보던 중 문자열끼리 대소관계가 비교가 된다라는 것을 듣고 바로 해결할 수 있었다.

풀이

연산자는 연산자 배열을 따로 만들어주어 관리해주었고, 순열을 돌리며 check 함수를 통해 연산자를 사이사이에 끼워넣었을때 문제가 없는지 확인하여 문제가 없다면 arr의 각 원소들을 문자열로 변환시켜 새로운 문자열에 담아주었다. 그리고 C++ STL에서 제공하는 max, min 함수를 통해 문제를 해결할 수 있었다.

max, min 함수가 정수형이나 실수형 자료형끼리의 비교만 가능한 줄 알았는데 문자열끼리의 비교도 가능하다는 것을 처음 알았다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using namespace std;

int n;
string maxi = "0";
string mini = "999999999";
int arr[10];
bool isused[11];
char oper[10];

bool check()
{
	bool flag = false;
	int idx = 0;
	
	for (int i = 0; i < n; i++)
	{
		if (oper[i] == '<')
		{
			if (arr[i] < arr[i + 1] == 0)
			{
				return false;
			}
		}
		else if (oper[i] == '>')
		{
			if (arr[i] > arr[i + 1] == 0)
			{
				return false;
			}
		}
	}

	return true;
}

void func(int k)
{
	if (k == n + 1)
	{
		if (check())
		{
			string s = "";
			for (int i = 0; i < n + 1; i++)
			{
				s += to_string(arr[i]);
			}
			maxi = max(maxi, s);
			mini = min(mini, s);
		}
		return;
	}

	for (int i = 0; i < 10; i++)
	{
		if (!isused[i])
		{
			isused[i] = true;
			arr[k] = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> oper[i];
	}

	func(0);

	cout << maxi << "\n" << mini;
}