백준 2529번 부등호(Python, C++)

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

2529번: 부등호

0~9 숫자 중 중복 없이 부등호 기호에 만족하는 문자열을 만들어야 한다. 

그리고 0 > 2 < 3 .... 경우 0뒤부터는 조건에 맞지 않으므로 더 이상 숫자를 넣을 필요없이 다른 경우로 넘어가면 된다. 

그리고 0부터 시작하므로 가장 첫번째로 완성된 문자열은 최솟값이고 가장 마지막에 만든 문자열이 최댓값이다.

문자열이 생성되는 과정을 설명하자면 첫번째가 0이면 0은 이미 사용했으므로 c[0]을 True값으로 만들고 다시 solve함수를 호출하여(재귀) 뒤에 만족하는 숫자를 1부터 9까지 사용자가 입력한 길이만큼 모든 경우의 수로 반복을 한 후 solve함수가 끝났을 때 c[0]을 다시 False값으로 바꾼 후 첫번째를 1로 설정하고 다시 앞의 과정을 반복한다. 이렇게 첫번째가 9일때까지 하면 만들 수 있는 문자열 중 최솟값과 최대값까지 구할 수 있게 된다.

 

 

 

<python>

n = int(input())
b = input().split()
c = [False]*10 # 0~9
mx, mn = "", ""

def possible(i,j,k): # 가능한지 불가능한지 판단해주는 함수
    if k == '<':
        return i<j
    if k == '>':
        return i>j
    return True

def solve(cnt, s):

    global mx, mn
    if cnt == n+1:
        if not len(mn): # mn이 비워져 있으면 최솟값에 s 넣기
            mn = s
        else: # mn에 값이 있으면 최댓값에 넣기
            mx = s
        return
    for i in range(10):# 0부터 9까지 
        if not c[i]: # c[i]이 false이면(중복 방지)
            if cnt==0 or possible(s[-1], str(i), b[cnt-1]):
                c[i]=True
                solve(cnt+1, s+str(i)) 
                # 만약 0 > ? 일 경우 ?에 올 숫자가 없으므로 solve함수가 끝나고 c[0]이 false가 되고 c[1]부터 다시 시작한다.
                c[i]=False


solve(0, "")
print(mx)
print(mn)

 

 

<c++>

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

int n; // 부등호 갯수
char b[9];
bool c[10] = { false, };
string mn, mx;

bool possible(int i, int j, char k) {
	if (k == '<')return i < j;
	if (k == '>')return i > j;
	return true;
}

void solve(int cnt, string s){
	if (cnt == n + 1) {
		if (!mn.size()) {
			mn = s;
		}
		else mx = s;
		return;
	}
	for (int i = 0; i < 10; i++) {
		if (c[i]) continue;
		if (cnt == 0 || possible(s[cnt - 1], i+'0', b[cnt - 1])) {
			c[i] = true;
			solve(cnt+1, s+to_string(i));
			c[i] = false;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	solve(0, "");
	cout << mx << '\n';
	cout << mn << '\n';
	return 0;
}