본문 바로가기

알고리즘

inequal

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

public class Main{ 
    // [이해] 부등호에 맞는 숫자열 출력,부등호에 들어가는 숫자는 0~9 
    // [입력] 부등호 개수, 부등호 
    // [출력] 부등호 관계만족하는 최대값, 최소값 
    // [설계] 최대값의 경우 (오름에서 내림으로 n개의 숫자에서 r개를 뽑되,출력하는 지점에서 기호를 검사해서 기호를 만족하는 경우에만 출력한다.) 
    // [설계] 최소값의 경우 (내림에서 내림으로 n개의 숫자에서 r개를 뽑되,출력하는 지점에서 기호를 검사해서 기호를 만족하는 경우에만 출력한다.)    public static void main(String[] args){ 
     
    // [추가] 전역에 flag=false를 만든다. 
    // [1] 기호 개수를 입력받는다. (n) 
    // [2] 기호 배열 생성(arr[n]) (string)(small,big) 
    // [3] 숫자 배열 생성(brr[n+1]) 
    // [4] 방문 테이블 생성(v[10])(0~9) boolean 
    // [5] f(depth) 
    //     여기에 넣어주면 좋다고 한다.(flag값을) 
    //     기저: depth가 숫자배열길이에 도달하면 출력하는 함수를 호출한다.//종료한다. 
    //     for(int i=9;i>=0;--) 
    //         만약 i가 방문안한거면 
    //            방문체크하고, brr[depth+1]에 i 넣어주고 
    //            f(depth+1) 호출하고 
    //            방문체크 해제해준다. 
    // 출력함수printArr() 
    // [] flag 가 true면 뭍지도 따지지도 말고 리턴한다. 
    // for(i=0 부터 기호 배열길이만큼) 
    //    arr[i] 를 기준으로 brr[i] 와 brr[i+1]을 비교 
    //    조건이 안 맞으면 리턴,   (small) brr[i] < brr[i+1] 이어야 하고 (big) brr[i]>brr[i+1] 관계가 성립해야함. 
    //  끝까지 조건이 맞아 반복문 다 돌았으면 조건에 맞게 숫자 출력(flag==true로 한다) 
     
    // v 배열 초기화 
    // 최소값 구하는 거에 대해서 위의 메소드 따로 만들어주고 for문 0부터 시작, 
    //  
    public static int n; 
    public static String[] arr; 
    public static int[] brr; 
    public static boolean[] v=new boolean[10]; 
    public static boolean flag=false;
    public static void main(String[] args) 
    { 
      Scanner scan = new Scanner(System.in); 
      n = scan.nextInt(); 
      arr = new String[n]; 
      brr = new int[n+1]; 
      for(int i=0;i<n;i++) 
      { 
        String x = scan.next(); 
        if(x=="<" || x.equals("<")) 
          arr[i]="small"; 
        else 
          arr[i]="big"; 
      } 
      f(0);
      init();flag=false;
      f2(0);
       
      // System.out.println(Arrays.toString(arr)); 
      scan.close(); 
    } 
    public static void init()
    {
      for(int i=0;i<10;i++)v[i]=false;
    }
    
    public static void f2(int depth) 
    { 
      if(flag==true)return;
      
      if(depth==n+1)
      { 
        printArr();
        return;
      }
      for(int i=0;i<=9;i++)
      {
        if(!v[i])
        {
          v[i]=true;
          brr[depth]=i;
          f2(depth+1);
          v[i]=false;
        }
      }
    }
    
    public static void f(int depth) 
    { 
      if(flag==true)return;
      
      if(depth==n+1)
      { 
        printArr();
        return;
      }
      for(int i=9;i>=0;i--)
      {
        if(!v[i])
        {
          v[i]=true;
          brr[depth]=i;
          f(depth+1);
          v[i]=false;
        }
      }
    }
    
    public static void printArr()
    {
      for(int i=0;i<arr.length;i++)
      {
        //<
        if(arr[i]=="small" && brr[i]>brr[i+1]){return;}
        if(arr[i]=="big" && brr[i]<brr[i+1]){return;}
      }
      
      for(int i=0;i<brr.length;i++)
      {
        System.out.print(brr[i]);
      }System.out.println();
     
      
      
      flag=true;
      return;
    }
}



'알고리즘' 카테고리의 다른 글

행렬뒤집기  (0) 2019.08.01
상자색 칠하기  (0) 2019.08.01
Class President  (0) 2019.08.01
Seat  (0) 2019.08.01
Offset  (0) 2019.08.01