[BAEKJOON]2529 부등호

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver1
• 문제내용:
  • 부등호 '<', '>'와 부등호 개수가 주어진다.
  • 각 자리 사이에 부등호를 넣어서 조건에 맞는 숫자중 최대 값과 최소 값을 구해라. 
• 사이트 주소: https://www.acmicpc.net/problem/2529

2529번: 부등호

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 여기에 참조하면된다.

문제 접근 방법

 이번 문제는 숫자0 ~ 9방문여부와 각 자리에 0 ~ 9 까지 뒤에 숫자랑 부등호와 비교해서 맞으면 그 다음 자리로  넘어가는식으로 함수 재호출을 구현 하면 된다. 마지막으로 조건에 맞는 숫자를 구했으면 그 숫자가 최대값이나 최소값에 맞게 저장하면 끝이다. 이번 문제 조건은 아래와 같이 구현 하면된다.

visited[i] == false && ((inequality[depth].equals("<") && i > Integer.parseInt(String.valueOf(number.charAt(depth))))
					|| (inequality[depth].equals(">") && i < Integer.parseInt(String.valueOf(number.charAt(depth)))))
               // 1. 방문 여부
               // 2. 앞뒤 부등호 조건이 만족할 경우

Code

Python

def make_inequality(depth, number):
    global max_value, min_value
    if depth == N:
        if int(number) > int(max_value):
            max_value = number
        if int(number) < int(min_value):
            min_value = number
        return
    
    for i in range(10):
    	#1. 0 ~ 9 방문 여부
	#2. 각 자리의 부등호와 뒤의 숫자랑 조건이 맞을 경우
        if (visited[i] == False and ((inequality[depth] == "<" and int(number[depth]) < i ) or 
                                     (inequality[depth] == ">" and int(number[depth]) > i ))):
            visited[i] = True
            make_inequality(depth + 1, number + str(i))
            visited[i] = False

# 첫째자리가 0이 올수 있기 때문에 문자열로 저장한다.
max_value = str(0)
min_value = str(10 ** 11)
N = int(input())
inequality = input().split()
visited = [False] * 10
for i in range(10):
    visited[i] = True
    make_inequality(0, str(i))
    visited[i] = False

print(max_value)
print(min_value)

Java

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


public class Main {
	
	// 첫째 자리가 0이 올수 있기때문에 문자열로 저장한다.
	static String max_value = String.valueOf(Long.MIN_VALUE);
	static String min_value =String.valueOf(Long.MAX_VALUE);
	static int N;
	static boolean[] visited = new boolean[10];
	static String[] inequality;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		inequality = new String[N];
		for (int i = 0; i < N; i++) {
			inequality[i] = st.nextToken();
		}
		for(int i = 0; i <= 9; i++) {
			visited[i] = true;
			make_inequality(0, String.valueOf(i));
			visited[i] = false;
		}
		System.out.println(max_value);
		System.out.println(min_value);
	}
	
	public static void make_inequality(int depth, String number) {
		if (N == depth) {
				
			if(Long.parseLong(number) > Long.parseLong(max_value)) {
				max_value = number;
			}
			if(Long.parseLong(number) < Long.parseLong(min_value)) {
				min_value = number;
			}
			return;
		}
		for(int i = 0; i <=9; i++) {
			//1. 0 ~ 9 방문 여부
			//2. 각 자리의 부등호와 뒤의 숫자랑 조건이 맞을 경우
			if(visited[i] == false && ((inequality[depth].equals("<") && i > Integer.parseInt(String.valueOf(number.charAt(depth))))
					|| (inequality[depth].equals(">") && i < Integer.parseInt(String.valueOf(number.charAt(depth)))))) {
				visited[i] = true;
				make_inequality(depth + 1, number + i);
				visited[i] = false;
			}
			
		}
	}

}