[알고리즘] 백준 2529 부등호 -백트래킹- 자바 코틀린

 

 

www.acmicpc.net/problem/2529

2529번: 부등호

 

 

백준 백트래킹 유형의 2529번 부등호 문제를 풀어봤습니다.

부등호가 주어지면 해당 부등호를 만족하는 숫자들 중 최댓값과 최솟값을 출력하면 되는 문제였습니다.

DFS 백트래킹을 사용하여 완전탐색 해주면 해결이 됩니다. 

 

풀이는 주석으로 적어놨고 다음과 같습니다.

 

[Java]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static int k; // 부등호 문자의 개수(2 ≤ k ≤ 9)
    private static boolean[] isVisited = new boolean[10]; // 0~9 숫자방문여부 (중복숫자불가하므로)
    private static char[] signs;
    private static List<String> result = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        signs = new char[k];
        for (int i = 0; i < k; i++) {
            signs[i] = sc.next().charAt(0);
        }
        dfs("", 0);
        Collections.sort(result);
        System.out.println(result.get(result.size() - 1)); //최댓값
        System.out.println(result.get(0)); //최솟값
    }

    private static void dfs(String num, int depth) { //처음 nums를 int[]로 접근했는데 String으로 하는게 간단해진다.
        if (depth == k + 1) {
            result.add(num);
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (depth == 0 || !isVisited[i] && compare(num.charAt(num.length() - 1) - '0', i, signs[depth - 1])) { //처음건 비교할게없으므로 통과 || 방문안한숫자 && 비교
                isVisited[i] = true;
                dfs(num + i, depth + 1);
                isVisited[i] = false;
            }
        }
    }

    private static boolean compare(int a, int b, char c) {
        if (c == '<') return a < b;
        else return a > b;
    }
}

 

 

[Kotlin]

import java.util.*


private var k // 부등호 문자의 개수(2 ≤ k ≤ 9)
        = 0
private val isVisited = BooleanArray(10) // 0~9 숫자방문여부 (중복숫자불가하므로)
private lateinit var signs: CharArray
private val result: MutableList<String> = ArrayList()

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    k = sc.nextInt()
    signs = CharArray(k)
    for (i in 0 until k) {
        signs[i] = sc.next()[0]
    }
    dfs("", 0)
    result.sort()
    println(result[result.size - 1]) //최댓값
    println(result[0]) //최솟값
}

private fun dfs(num: String, depth: Int) { //처음 nums를 int[]로 접근했는데 String으로 하는게 간단해진다.
    if (depth == k + 1) {
        result.add(num)
        return
    }
    for (i in 0..9) {
        if (depth == 0 || !isVisited[i] && compare(num[num.length - 1] - '0', i, signs[depth - 1])) { //처음건 비교할게없으므로 통과 || 방문안한숫자 && 비교
            isVisited[i] = true
            dfs(num + i, depth + 1)
            isVisited[i] = false
        }
    }
}

private fun compare(a: Int, b: Int, c: Char): Boolean {
    return if (c == '<') a < b else a > b
}

 

github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%202529%20%EB%B6%80%EB%93%B1%ED%98%B8%20-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-

mtjin/algorithm_practice

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!