[백준] 2529 : 부등호

How to solve

이 문제는 0~9 의 수 중 각 부등호에 넣을 수 있는 수를 구하는 것이다.

부등호가 성립하도록 넣어지는 수는 중복되지 않는다.

​

Tip1.

순열은 구할 때는,

next_permutation() prev_permutation() 함수를 활용해서 구한다.

​

Tip2.

부등호가 성립하는지 확인하는 함수를 만든다.

​

풀이 순서

본 문제는 다음과 같은 순서로 풀이한다.

1. 순열의 최대 값을 maxVal에 저장한다.

2. maxVal의 순열 값의 부등호 성립여부를 연산하여, 성립하면 return 한다.

prev_permutation()으로 이전 순열 값을 찾으며, 1-2 과정을 반복한다.

3. 순열의 최소 값을 minVal에 저장한다.

4. 순열의 최소 값 부터 시작하여 next_permutation()으로 다음 순열 값을 찾으며,

그 순열 값의 부등호 성립여부를 연산하여, 성립하면 return 한다.

​

상세한 풀이과정은 다음과 같다.

​

1. 순열의 최대 값을 maxVal에 저장한다.

예를들어 k=2인 경우,

maxVal[0] = 9

maxVal[1] = 8

maxVal[2] = 7 이 된다.

​

2. 현재 maxVal 값의 부등호 성립여부를 확인한다.

다음 과정을 prev_permuation() 함수를 이용하여 이전 순열을 찾으며 반복한다.

// 부등호 만족 체크  
bool check(vector<int> &v){

	for(int i=0; i<N; i++){
		if(oper[i] == '<'){
			if(v[i]>v[i+1]){
				return false;
			}
		}
		else if(oper[i] == '>'){
			if(v[i]<v[i+1]){
				return false;
			}
		}
	}
	return true;
}

3.순열의 최소 값을 minVal에 저장한다.

예를들어 k=2인 경우,

minVal[0] = 0

minVal[1] = 1

minVal[2] = 2 이 된다.

​

4. 현재 minVal 값의 부등호 성립여부를 확인한다.

다음 과정을 next_permuation() 함수를 이용하여 다음 순열을 찾으며 반복한다.

​

Problem

부등호 성공출처분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

8847

4518

3186

50.181%

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

예제 입력 1

2

< >

예제 출력 1

897

021

Solution

// 2529 부등호

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

#define MAX 10

using namespace std;
 
int N;

vector <int> maxVal;
vector <int> minVal;
char oper[11];

long long large;
long long small;

// 부등호 만족 체크  
bool check(vector<int> &v){

	for(int i=0; i<N; i++){
		if(oper[i] == '<'){
			if(v[i]>v[i+1]){
				return false;
			}
		}
		else if(oper[i] == '>'){
			if(v[i]<v[i+1]){
				return false;
			}
		}
	}
	return true;
}

int main(){
	
	// input 
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf(" %c", &oper[i]);
	}
	
	// solution
	// max
	for(int i=9; i>9-(N+1); i--){
		maxVal.push_back(i);
	}
	
	do{
		if(check(maxVal)){
			break;
		}	
	}while(prev_permutation(maxVal.begin(), maxVal.end()));
	
	// min
	for(int i=0; i<=N; i++){
		minVal.push_back(i);
	}
	do{
		if(check(minVal)){
			break;
		}	
	}while(next_permutation(minVal.begin(), minVal.end()));
	
	// print
	for(int i=0; i<=N; i++){
		printf("%d", maxVal[i]);
	}
	printf("\n");
	for(int i=0; i<=N; i++){
		printf("%d", minVal[i]);
	}
} 

Reference

www.acmicpc.net/problem/2529

2529번: 부등호