[Algorithm] 순열 조합

순열

N : 자연수

R : 뽑을 갯수

nPr 구하기!

 

자연수

import org.junit.jupiter.api.Test
import java.util.*

class Permutation {

    private var N: Int = 0
    private var R: Int = 0
    private fun dfs(curNum: Int, visited: BooleanArray, depth: Int, strBuilder: StringBuilder, answerList: LinkedList<Int>) {
        strBuilder.append(curNum)

        if (depth == R) {
            answerList.add(strBuilder.toString().toInt())
            strBuilder.setLength(strBuilder.length - 1)
            return
        }

        for (i in 1 .. N) {
            if (!visited[i]) {
                visited[i] = true
                dfs(i, visited, depth + 1, strBuilder, answerList)
                visited[i] = false
            }
        }

        strBuilder.setLength(strBuilder.length - 1)

    }

    @Test
    internal fun testPermutation() {
        N = 5
        R = 3

        val visited = BooleanArray(N + 1)
        val strBuilder = StringBuilder(R + 1)
        val answer = LinkedList<Int>()

        for (i in 1 .. N) {
            visited[i] = true
            dfs(i, visited, 1, strBuilder, answer)
            visited[i] = false
        }

        println(answer.size)

        for (num in answer) {
            println(num)
        }
    }
}

 

문자열

private fun stringDFS(curIdx: Int, visited: BooleanArray, depth: Int, strBuilder: StringBuilder, str: String, answerList: LinkedList<String>) {
    visited[curIdx] = true
    strBuilder.append(str[curIdx])
    if (strBuilder.length == depth) {
        answerList.add(strBuilder.toString())
        visited[curIdx] = false
        strBuilder.setLength(strBuilder.length - 1)
        return
    }

    for (i in str.indices) {
        if (!visited[i]) {
            stringDFS(i, visited, depth, strBuilder, str, answerList)
        }
    }

    visited[curIdx] = false
    strBuilder.setLength(strBuilder.length - 1)
}

@Test
internal fun testStringPermutation() {
	// 정렬해주는게 국룰임.
    val str = "ABCDE".toCharArray().sorted().joinToString("")
    // 5개중 3개 뽑아보셈
    val targetLen = 3
    val visited = BooleanArray(str.length){false}
    val stringBuilder = StringBuilder()
    val answer = LinkedList<String>()

    for (i in str.indices) {
        stringDFS(i, visited, targetLen, stringBuilder, str, answer)
    }
    // 5 * 4 * 3 == 60
    println(answer.size)
    
    for (element in answer) {
        println(element)
    }
}

배열

import java.io.BufferedReader
import java.io.InputStreamReader

// depth 가 곧 이번에 진입한 index
// Base condition: targetDepth 와 현재 depth 가 같은 경우
fun dfs (curIdx: Int, depth: Int,  targetDepth: Int, arr: IntArray, answer: IntArray, stringBuilder: StringBuilder) {
	// 이미 삽입된 상태로 오는거라 depth 충족시 바로 out.
    if (depth == targetDepth) {
        for (num in answer) stringBuilder.append("$num ")
        stringBuilder.appendLine()
        return
    }

    for (idx in curIdx until arr.size) {
        // Q. 어떻게 바로 여기서 모든 구간을 다 돌아보지?
        // A. depth 가 무조건 위치를 결정하고
        // arr[idx] 가 시작위치를 fix 해버림.
        answer[depth] = arr[idx]
        dfs(idx, depth + 1, targetDepth, arr, answer, stringBuilder)
    }
}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val stringBuilder = StringBuilder()

    val (N, M) = bufferedReader.readLine().split(" ").map(String::toInt)
    val arr = bufferedReader.readLine().split(" ").map(String::toInt).toIntArray()
    arr.sort()

    val answer = IntArray(M){0}

    dfs(0, 0, M, arr, answer, stringBuilder)

    println(stringBuilder.toString())

}

조합

nCr 구하기!

자연수

import org.junit.jupiter.api.Test
import java.util.*

class Combination {
    private var N : Int = 0
    private var R : Int = 0

    private fun dfs(curNum: Int, depth: Int, strBuilder: StringBuilder, answer: LinkedList<Int>) {
        strBuilder.append(curNum)

        if (depth == R) {
            answer.add(strBuilder.toString().toInt())
            strBuilder.setLength(depth - 1)
            return
        }
        for (i in curNum + 1 .. N) {
            dfs(i, depth + 1, strBuilder, answer)
        }

        strBuilder.setLength(depth - 1)

    }
    @Test
    internal fun testCombination() {
        N = 5
        R = 3

        val stringBuilder = StringBuilder(R + 1)
        val answer = LinkedList<Int>()
		
        // 1부터 N까지 수에 대해
        
        for (i in 1 .. N) {
            dfs(i, 1, stringBuilder, answer)
        }

        println("Count: ${answer.size}")
        for (num in answer) {
            println(num)
        }
    }
}

 

 

문자열

private fun stringDFS(curIdx: Int, depth: Int, strBuilder: StringBuilder, str: String, answer: LinkedList<String>) {
    strBuilder.append(str[curIdx])

    if (strBuilder.length == depth) {
        answer.add(strBuilder.toString())
        strBuilder.setLength(strBuilder.length - 1)
        return
    }

    for (i in curIdx + 1 until str.length) {
        stringDFS(i, depth, strBuilder, str, answer)
    }

    strBuilder.setLength(strBuilder.length - 1)
}

@Test
internal fun testStringCombination() {
    val str = "ABCDE"
    // 5개중 3개 뽑기

    val targetLen = 3
    val stringBuilder = StringBuilder()
    val answer = LinkedList<String>()

    for (i in str.indices) {
        stringDFS(i, targetLen, stringBuilder, str, answer)
    }

    for (element in answer) {
        println(element)
    }
    // ABC
    // ABD
    // ABE
    // ACD
    // ACE
    // ADE
    // BCD
    // BCE
    // BDE
    // CDE
}