[BOJ]2529번: 부등호 (c++)

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

2529번: 부등호

 

방법 1: 정렬을 이용하여 dfs를 2번 시행하기 (20200601 추가)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string numbers = "9876543210";

// 두 문자의 크기를 c를 기준으로 판단하여 bool 반환
bool inline check(char ineuql, char A, char B)
{
	return (ineuql == '<') ? (A < B) : (A > B);
}

bool perm(vector<char> &inequal, vector<bool> &visit, string answer, int N, int cnt)
{
	// N개의 자리를 모두 완성하면 출력 후 종료
	if (cnt == N)
	{
		cout << answer << '\n';
		return true;
	}

	// numbers 문자열을 N번째 자리까지 탐색
	for (int i = 0; i < N; ++i)
	{
		if (!visit[i])
		{
			// 첫번째 자리이거나, 조건에 부합하면
			if (cnt == 0 || check(inequal[cnt - 1], answer[cnt - 1], numbers[i]))
			{
				visit[i] = true;
				/*
					한번이라도 성공하면 종료
					오름차순/내림차순 문자열을 dfs탐색하기 때문에, 
					가장 처음에 얻은 결과가 가장 작은/큰 값임.
				*/
				if (perm(inequal, visit, answer + numbers[i], N, cnt + 1))
				{
					return true;
				}
				visit[i] = false;
			}
		}
	}
	return false;
}

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

	// 입력
	int K;
	cin >> K;
	vector<char> inequal(K);
	for (int i = 0; i < K; ++i)
	{
		cin >> inequal[i];
	}

	vector<bool> visit(K + 1);
	
	// 내림차순 정렬된 numbers 문자열을 문제조건대로 K + 1개만큼 조합하기.
	perm(inequal, visit, "", K + 1, 0);
	

	// visit벡터를 false로 채우기
	fill(visit.begin(), visit.end(), 0);
	// 오름차순 정렬
	sort(numbers.begin(), numbers.end());
	

	// 오름차순 정렬된 numbers 문자열을 문제조건대로 K + 1개만큼 조합하기. 
	perm(inequal, visit, "", K + 1, 0);
	
	return 0;
}

 

방법 2: dfs함수 내에서 최대/최소를 모두 구하기

코드 더보기

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 10;
bool check[MAX];
char max_num[MAX + 1] = {-1, };
char min_num[MAX + 1] = {-1, };

// 두 숫자의 크기를 c를 기준으로 판단하여 bool 반환
bool comp(int num1, int num2, char c)
{
	if (c == '<')
	{
		return num1 < num2;
	}
	else if (c == '>')
	{
		return num1 > num2;
	}
	return false;
}

// 첫번째 문자배열이 나타내는 수가 더 크면 true 반환
bool first_is_bigger(char first[], char second[], int N)
{
	for (int i = 0; i < N; ++i)
	{
		if (first[i] > second[i])
		{
			return true;
		}
		else if (first[i] < second[i])
		{
			return false;
		}
	}
	return false;
}

// 배열의 값 복사
void copy_array(char to[], char from[], int N)
{
	for (int i = 0; i < N; ++i)
	{
		to[i] = from[i];
	}
}

void go(char inequal[], char numbers[], int N, int depth)
{
	// N개의 숫자 조합을 완성하면
	if (depth == N)
	{
		// max 판단이 처음이거나, max < numbers 일때
		if (max_num[0] == -1 || first_is_bigger(numbers, max_num, N))
		{
			copy_array(max_num, numbers, N);
		}
		// min 판단이 처음이거나, min > numbers 일때
		if (min_num[0] == -1 || first_is_bigger(min_num, numbers, N))
		{
			copy_array(min_num, numbers, N);
		}
		return;
	}

	// 0 ~ 9 의 숫자 중에서 조건에 일치하는 숫자를 조합
	for (int i = 0; i < 10; ++i)
	{
		if (!check[i])
		{
			// 첫번째 선택이거나, 이전 숫자와 현재 숫자가 조건에 일치하면 선택
			if (depth == 0 || comp(numbers[depth - 1] - '0', i, inequal[depth - 1]))
			{
				check[i] = true;
				numbers[depth] = i + '0';
				go(inequal, numbers, N, depth + 1);
				check[i] = false;
			}
		}
	}
}

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

	// 입력
	int k;
	cin >> k;
	char inequal[MAX];
	for (int i = 0; i < k; ++i)
	{
		cin >> inequal[i];
	}

	// dfs로 가능한 숫자 조합 
	char numbers[MAX] = {0,};
	go(inequal, numbers, k + 1, 0);

	// 출력
	cout << max_num << '\n';
	cout << min_num << '\n';

	return 0;
}

 

 

10일 전쯤에 방법2로 먼저 풀었던 문제인데,

더 좋은 풀이를 들고왔다!

 

TIP  모든 숫자를 조합할 필요가 없다. 

방법 2는 숫자 0~9를 모두 조합하면서 최소/최대값을 찾았지만 사실 그럴필요가 없다

ex)
2
< >

위처럼 예제가 주어지면, 출력해야할 결과는 3자리 숫자열이다.

그런데 숫자 10개를 일일이 다 찾아봐야할 필요가 있을까? --> NO

그리고 어차피 양 끝값 (최소값/최대값)이 필요한데, 중간을 훑을 필요가 있을까? --> NO

 

최대값은 987 부터, 최소값은 012 부터 찾으면 된다!

어차피 조건에 부합하는 숫자는 최대값은 9, 8, 7 안에서 조합될 것이고

최소값은 0, 1, 2 안에서 조합될 것이기 때문이다.

 

따라서 최대값 구할때 dfs 한번 돌리고

오름차순 정렬 함 해주고 최소값 구할때 dfs 한번 돌리면 된다!

 

 

 

방법 2 설명 더보기

 

 

string을 썼다면 좀더 코드가 간결했을 것이다. 

어쩌다 보니 char[] 배열을 써서 코드가 좀 길어짐..

 

TIP_다른방법

897 
021

출력이 이런식으로 앞에 0을 붙인 string형태로 되어야 한다.

즉, 사전식 정렬을 이용할 수 있다.

 

이 경우에는 가능한 모든 조합을 vector에 저장하고, 

다음과 같이 최소, 최대값을 골라서 출력하면 된다.

auto min_max = minmax_element(vector.begin(), vector.end());
cout << *min_max.second << '\n';
cout << *min_max.first << '\n';