부등호 (정올 2570, 백준 2529 )

부등호 (정올 2570, 백준 2529 ) 풀이 

문제 링크

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

2529번: 부등호

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1831&sca=5030 

JUNGOL

코드 전문 (java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
	static boolean[] vis;
	static int k;
	static LinkedList<String> ans=new LinkedList<String>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		k=Integer.parseInt(br.readLine());
		vis=new boolean[10];
		String[] input=br.readLine().split(" ");
		for(int i=9;i>=0;i--) {
			vis[i]=true;
			dfs(input,i+"",0);
			vis[i]=false;
		}
		System.out.println(ans.get(0));
		System.out.println(ans.get(ans.size()-1));
	}
	private static void dfs(String[] input, String now, int idx) {
		//System.out.println(now+"!"+input[idx]);
		if(idx==k) {
			ans.add(now);
			return;
		}
		if(input[idx].equals(">")) {
			for(int i=now.charAt(idx)-'0'-1;i>=0;i--) {
				if(vis[i])continue;
				vis[i]=true;
				dfs(input, now+i, idx+1);
				vis[i]=false;
			}
		}else {
			for(int i=9;i>now.charAt(idx)-'0';i--) {
				if(vis[i])continue;
				vis[i]=true;
				dfs(input, now+i, idx+1);
				vis[i]=false;
			}
		}
	}
}

 

설명

간단한 DFS

순서를 잘 맞추어 재귀를 돌린 후 리스트에 추가하면 최소,최대를 위한 정렬을 하지 않아도 된다.