[백준 - Java] 2529번 - 부등호

2529번 - 부등호

 

• main, dfs, comp 함수로 구성
• dfs 함수는 재귀적으로 사용 (void)
• comp 함수는 왼쪽, 오른쪽 정수가 부등호에 부합하는지 true, false로 반환 (boolean)

 

<코드>

import java.io.*;
import java.util.*;

public class Main {
	static int k;
	static boolean[] visit;
	static List<String> output = new ArrayList<>();
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		sb = new StringBuilder();
		
		k = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < k; i++) {
			sb.append(st.nextToken());
		}
		
		visit = new boolean[10]; //중복 방지 
		dfs("", 0);
		
		Collections.sort(output); //List 타입 배열을 정렬
		System.out.println(output.get(0)); //최솟값
		System.out.println(output.get(output.size()-1)); //최댓값
		
	}
	
	public static void dfs(String n, int dep) {
		//0 1 2 3 4 5 6 7 8 9 => 10개 
		if(dep == k+1) { //탐색 끝
			output.add(n);
			return ;
		}
		
		for(int i = 0; i <= 9; i++) {
			//dep == 0은 정수의 첫 시작일 경우를 대비해서 ||로 조건문에 포함됨.
			if(dep == 0 || !visit[i] && comp(n.charAt(n.length()-1) - '0', i, sb.charAt(dep -1))) {
				visit[i] = true;
				dfs(n + i , dep + 1); //재귀적 
				visit[i] = false;
			}
		}
	}
	
	public static boolean comp(int a, int b, char c) {
		if(c == '>') return a > b;
		else return a < b;
	}
}

 

<주요 코드>

if(dep == 0 || !visit[i] && comp(n.charAt(n.length()-1) - '0', i, sb.charAt(dep -1))) {
	visit[i] = true;
	dfs(n + i , dep + 1); //재귀적 
	visit[i] = false;
}

if문의 조건식을 작성하는 것이 이 문제에서 가장 핵심이라고 생각합니다. 

dep == 0 은 처음으로 저장되는 정수, 즉, 다음 정수와 비교할 정수가 없음을 의미합니다. 때문에 ||(OR)을 사용하여 dep가 0인 경우 comp 함수 호출을 생략합니다. 

!visit[i]은 정수의 중복 사용을 방지하기 위해 사용됩니다. 만약 정수의 중복 사용이 가능하다면 visit 배열 자체가 필요 없습니다. 

마지막으로 comp 함수입니다. 

첫 번째 매개변수는 바로 앞에 사용된 정수입니다. 두 번째 매개변수는 현재 정수(i)입니다. 세 번째 매개변수는 부등호입니다.  변수 n은 String 타입이므로 바로 앞에 사용된 정수를 찾기 위해 charAt(n.length() - 1)을 사용하고 이를 int 타입으로 바꾸기 위해 '0'을 빼줍니다. 

 

<알게 된 점>

static List<String> output = new ArrayList<>();

Collections.sort(output);

List 타입 배열을 정렬하기 위해 Collections 클래스가 사용된다는 점을 알게 되었습니다.

 

2022.08.16

감사합니다!