C++ / 백준 / 2529 / 부등호

문제

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

2529번: 부등호

문제풀이

처음에는 작은 수부터 모든 경우의 수를 돌면서 판별을 했더니 답은 맞았지만, 100456KB / 136ms라는 결과가 나왔다..

그래서 다른 답들을 봤더니 큰 수가 나오자마자 중단하고, 

작은 수부터 큰 수로 탐색하면서 중간 과정을 자르고 탐색을 하길래 참고하였다.

 

0부터 9까지의 수를 이용하여 해당 부등호에 맞게 배치하면 된다.

큰 숫자 먼저 찾을 것이기 때문에 9부터 0까지 순서대로 들어간 num 벡터를 만든다.

 

void biggest() {
	do {
		for (idx = 1; idx <= k; ++idx) {
			char sign = input[idx - 1];
			if (sign == '<') {
				if (num[idx - 1] >= num[idx]) {
					break;
				}
			}
			else if (sign == '>') {
				if (num[idx - 1] <= num[idx]) {
					break;
				}
			}
		}
		if (idx == k + 1) {
			for (idx = 0; idx <= k; ++idx) {
				cout << num[idx];
			}
			cout << '\n';
			return;
		}
	} while (prev_permutation(num.begin(), num.end()));
}

모든 숫자를 탐색하기 위해 prev_permutation함수를 이용한다.

내림차순으로 숫자를 탐색하면서 부등호가 맞는지 판별한다.

부등호를 input벡터로 받았고 하나씩 나누어 sign 변수에 저장한다.

해당 부등호가 맞지 않으면 바로 중단하여 다음 숫자를 판별한다.

만약 모든 부등호가 맞다면 (idx가 k+1이라면) 현재 숫자를 출력하고 함수를 종료한다.

 

가장 큰 수를 출력했으므로 이번엔 가장 작은 수를 출력해야 한다.

biggest함수와 마찬가지로 smallest함수도 똑같다.

다만 다른 점은 오름차순으로 정렬을 하고 prev가 아닌 next_permutation 함수를 사용해야 한다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int k, idx;
vector<char>input;
vector<int>num(10, 0);

void biggest() {
	do {
		for (idx = 1; idx <= k; ++idx) {
			char sign = input[idx - 1];
			if (sign == '<') {
				if (num[idx - 1] >= num[idx]) {
					break;
				}
			}
			else if (sign == '>') {
				if (num[idx - 1] <= num[idx]) {
					break;
				}
			}
		}
		if (idx == k + 1) {
			for (idx = 0; idx <= k; ++idx) {
				cout << num[idx];
			}
			cout << '\n';
			return;
		}
	} while (prev_permutation(num.begin(), num.end()));
}

void smallest() {
	sort(num.begin(), num.end());
	do {
		for (idx = 1; idx <= k; ++idx) {
			char sign = input[idx - 1];
			if (sign == '<') {
				if (num[idx - 1] >= num[idx]) {
					break;
				}
			}
			else if (sign == '>') {
				if (num[idx - 1] <= num[idx]) {
					break;
				}
			}
		}
		if (idx == k + 1) {
			for (idx = 0; idx <= k; ++idx) {
				cout << num[idx];
			}
			return;
		}
	} while (next_permutation(num.begin(), num.end()));
}

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

	cin >> k;

	input = vector<char>(k, ' ');

	for (idx = 0; idx < k; ++idx)
		cin >> input[idx];

	for (idx = 0; idx < 10; ++idx)
		num[9 - idx] = idx;

	biggest();
	smallest();
}