[BOJ] 2529. 부등호

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int N;
	static Long max=Long.MIN_VALUE;
	static Long min=Long.MAX_VALUE;
	static int maxArr[];
	static int minArr[];
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		int arr[]=new int[N+1];
		char oper[]=new char[N];
		boolean check[]=new boolean[10];
		maxArr=new int[N+1];
		minArr=new int[N+1];
		
		for (int i = 0; i < N; i++) 
			oper[i]=sc.next().charAt(0);
		
		for (int i = 0; i < 10; i++) {
			arr[0]=i;
			check[i]=true;
			go(0,oper,check,arr,i);
			check[i]=false;
			arr[0]=0;
		}
		for (int i = 0; i < N+1; i++) {
			System.out.print(maxArr[i]);
		}
		System.out.println();
		for (int i = 0; i < N+1; i++) {
			System.out.print(minArr[i]);			
		}
		
	}
	
	public static void go(int index,char oper[],boolean check[],int arr[],int last) {
		if(index==N) {
			long val=0;
			for (int i = 0; i < N+1; i++) {
				val+=arr[i]*Math.pow(10, N-i);				
			}

			if(val>max) {
				max=val;
				for (int i = 0; i < N+1; i++) {
					maxArr[i]=arr[i];					
				}
			}
			if(val<min) {
				min=val;
				for (int i = 0; i < N+1; i++) {
					minArr[i]=arr[i];					
				}
			}
			return;
		}
		
		if(oper[index]=='<') {
			for (int i = last+1; i < 10; i++) {
				if(!check[i]) {
					check[i]=true;
					arr[index+1]=i;
					go(index+1,oper,check,arr,i);
					check[i]=false;
					arr[index+1]=0;
				}
			}
		}else {
			for (int i = 0; i < last; i++) {
				if(!check[i]) {
					check[i]=true;
					arr[index+1]=i;
					go(index+1,oper,check,arr,i);
					check[i]=false;
					arr[index+1]=0;
				}
			}
		}
	}
}