[Kotlin] 알고리즘

숫자 더하기

fun main() = with(System.`in`.bufferedReader()) {
    // 첫 번째 입력은 사용하지 않으므로 바로 다음 입력으로 넘어갑니다.
    readLine()
    // 두 번째 입력 받은 문자열의 각 문자를 숫자로 변환한 후, 그 합계를 구합니다.
    println(readLine().sumOf { it.toString().toInt() })
}

중복 문자 제거

class Solution {
    fun solution(my_string: String): String {
       // 입력받은 문자열에서 중복을 제거한 문자 집합을 만들고, 이를 다시 문자열로 변환하여 반환합니다.
       return my_string.toSet().joinToString("")
    }
}

배열 병합

class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    	// System.arraycopy() 함수를 사용하여 nums2의 모든 요소를 nums1의 m 인덱스 위치부터 시작하여 복사합니다. 
        // 이렇게 하면 nums1의 끝에 nums2가 병합됩니다.
        System.arraycopy(nums2, 0, nums1, m, n)
        nums1.sort()
    }
}

문자거리

fun main() = System.`in`.bufferedReader().run {
    // 입력 받은 두 문자열 s와 t를 공백을 기준으로 분리해서 저장
    val (s, t) = readLine().split(' ')
    // 각 문자와 타겟 문자 사이의 거리를 저장할 배열 초기화
    val answer = IntArray(s.length) { 0 }

    // 왼쪽에서 오른쪽으로 거리 계산
    var distance = Int.MAX_VALUE
    // 문자열 s의 각 문자를 순회하며 거리 계산
    s.forEachIndexed { index, c ->
        if (c == t[0]) distance = 0 // 현재 문자가 타겟 문자와 같으면 거리는 0
        else if (distance != Int.MAX_VALUE) distance++ // 그렇지 않고 이전에 타겟 문자를 찾았다면 거리 1 증가
        
        answer[index] = distance // 계산된 거리를 결과 배열에 저장
    }

    // 오른쪽에서 왼쪽으로 거리 계산 및 업데이트
    distance = Int.MAX_VALUE
    // 문자열 s를 뒤에서부터 순회하며 거리 계산
    s.indices.reversed().forEach { index ->
        if (s[index] == t[0]) distance = 0 // 현재 문자가 타겟 문자와 같으면 거리는 0
        else if (distance != Int.MAX_VALUE) distance++ // 그렇지 않고 이전에 타겟 문자를 찾았다면 거리 1 증가
        
        // 왼쪽에서 계산한 값과 비교하여 더 작은 값으로 업데이트
        answer[index] = minOf(answer[index], distance)
    }

    // 계산된 거리를 공백으로 구분하여 출력
    println(answer.joinToString(" "))
}

문자열 압축

fun main() = System.`in`.bufferedReader().run {
    val input = readLine()!! // 문자열 입력 받기
    val result = input.foldIndexed(StringBuilder()) { index, acc, current ->
        // 마지막 문자 또는 현재 문자가 다음 문자와 다를 때 처리
        if (index == input.length - 1 || current != input[index + 1]) {
            acc.append(current) // 현재 문자를 누적
            // 연속된 문자열의 길이 계산 (현재 인덱스에서 이전에 같은 문자가 마지막으로 나타난 위치를 뺌)
            val length = index - acc.lastIndexOf(current.toString()) + 1
            if (length > 1) acc.append(length) // 연속 길이가 1보다 크면 길이도 누적
        }
        acc // 누적된 결과 반환
    }
    
    println(result.toString()) // 결과 출력
}

암호

fun main() = System.`in`.bufferedReader().run {
    val n = readLine().toInt()
    var s = readLine()

    repeat(n) {
        s.take(7) // 첫 7개 문자 가져오기
            .map { if (it == '#') '1' else '0' } // '#'을 '1'로, '*'을 '0'로 변환
            .joinToString("") // 문자 리스트를 문자열로 변환
            .toInt(2) // 2진수 문자열을 정수로 변환
            .toChar() // ASCII 값에 해당하는 문자로 변환
            .let(::print) // 결과 출력
        s = s.drop(7) // 처리된 첫 7개 문자 제거
    }
}

구간합 구하기

fun main() = with(System.`in`.bufferedReader()) {
    // n은 배열의 크기, m은 쿼리의 수를 의미합니다.
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val arr = IntArray(n + 1)
    // 입력 받은 문자열을 숫자 배열로 변환하면서 누적 합을 계산합니다.
    readLine().split(" ").forEachIndexed { index, value ->
        arr[index + 1] = arr[index] + value.toInt()
    }
    // m개의 쿼리를 처리합니다.
    repeat(m) {
        val (i, j) = readLine().split(" ").map { it.toInt() }
        // i부터 j까지의 구간합을 출력합니다.
        println(arr[j] - arr[i - 1])
    }
}

투 포인터

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    var count = 0
    var end = 0
    var sum = 0

    // start를 1부터 N까지 반복하면서 end를 이동시키며 검사
    for (start in 1..N) {
        while (end < N && sum < N) {
            end++
            sum += end
        }
        if (sum == N) count++
        sum -= start // start를 다음 숫자로 이동시키기 전에 현재 start 값을 sum에서 뺌
    }

    println(count)
}

fun main() = with(System.`in`.bufferedReader()) {
    var n = readLine().toInt() // n은 재료의 총 개수입니다.
    var m = readLine().toInt() // m은 만들고자 하는 갑옷의 번호 합입니다.
    val materials = readLine().split(" ").map { it.toInt() }.sorted() // 재료의 번호들을 읽어 배열로 만든 후 오름차순으로 정렬합니다.

    var count = 0
    var start = 0
    var end = n - 1

    while (start < end) {
     	// 현재 시작점과 끝점에 위치한 재료의 번호 합을 계산합니다.
        val sum = materials[start] + materials[end]

        when {
            // 계산된 합이 m과 같다면 갑옷을 만들 수 있는 조합이므로 count를 증가시키고, 포인터를 이동합니다.
            sum == m -> {
                count++
                start++
                end--
            }
             // 계산된 합이 m보다 작다면 합을 증가시키기 위해 시작점을 오른쪽으로 이동합니다.
            sum < m -> start++
            // 계산된 합이 m보다 크다면 합을 감소시키기 위해 끝점을 왼쪽으로 이동합니다.
            else -> end--
        }
    }
    // 최종적으로 가능한 갑옷 조합의 수를 출력합니다.
    println(count)
}

class Solution {
    // 주어진 문자열 s가 회문인지 여부를 판단하는 함수
    fun isPalindrome(s: String): Boolean {
        // 문자열의 시작 인덱스
        var left = 0
        // 문자열의 끝 인덱스
        var right = s.length - 1

        // 두 포인터가 서로 교차할 때까지 반복
        while (left < right) {
            // 왼쪽 포인터가 가리키는 문자가 알파벳 또는 숫자가 아닐 경우
            while (left < right && !s[left].isLetterOrDigit()) {
                left++ // 왼쪽 포인터를 오른쪽으로 이동
            }
            // 오른쪽 포인터가 가리키는 문자가 알파벳 또는 숫자가 아닐 경우
            while (left < right && !s[right].isLetterOrDigit()) {
                right-- // 오른쪽 포인터를 왼쪽으로 이동
            }

            // 현재 왼쪽과 오른쪽 포인터가 가리키는 문자를 비교 (대소문자 무시)
            if (s[left].toLowerCase() != s[right].toLowerCase()) {
                return false // 문자가 일치하지 않으면 회문이 아님
            }

            // 포인터를 각각 한 칸씩 이동
            left++
            right--
        }

        // 모든 문자들이 대칭이라면 회문이므로 true 반환
        return true
    }
}

슬라이딩 윈도우

fun lengthOfLongestSubstring(s: String): Int {
	var maxLength = 0
	var start = 0
    val charIndexMap = mutableMapOf<Char, Int>()

	for (end in s.indices) {
    	val currentChar = s[end]

		// 중복된 문자가 있으면 start를 이동시킴
    	if (charIndexMap.containsKey(currentChar)) {
    		// start를 중복된 문자 이후로 이동시킴
        	start = maxOf(start, charIndexMap[currentChar]!! + 1)
    	}

		// 현재 문자의 위치를 갱신
    	charIndexMap[currentChar] = end

		// 윈도우 크기를 계산하여 최대값 갱신
    	maxLength = maxOf(maxLength, end - start + 1)
	}

	return maxLength
}

fun main() = with(System.`in`.bufferedReader()) {
    // s는 DNA 문자열의 길이, p는 검사할 윈도우의 길이
    val (s, p) = readLine().split(" ").map { it.toInt() }
    // DNA 문자열 입력받음
    val dna = readLine()
    // 각 문자(A, C, G, T)가 윈도우에 최소 몇 개 있어야 하는지 입력받음
    val (a, c, g, t) = readLine().split(" ").map { it.toInt() }
    // 초기 윈도우(ss) 설정
    val ss = dna.substring(0, p)
    // 초기 윈도우 내의 A, C, G, T의 개수 계산
    var (sa, sc, sg, st) = listOf(
        ss.count { it == 'A' },
        ss.count { it == 'C' },
        ss.count { it == 'G' },
        ss.count { it == 'T' }
    )
    // 조건을 만족하는 윈도우의 개수를 세는 카운터
    var cnt = 0
    // 윈도우의 시작점과 끝점
    var start = 0
    var end = p - 1
    // 윈도우를 DNA 문자열 끝까지 슬라이드
    while (end <= s - 1) {
        // 현재 윈도우가 조건을 만족하는지 확인
        if (sa >= a && sc >= c && sg >= g && st >= t) {
            cnt++
        }
        // 윈도우의 시작점 문자에 따라 카운트 감소
        when (dna[start]) {
            'A' -> sa--
            'C' -> sc--
            'G' -> sg--
            'T' -> st--
        }
        // 윈도우를 한 칸 오른쪽으로 이동
        start++
        end++
        if (end >= s) break  // 윈도우의 끝점이 DNA 문자열의 끝을 넘어서면 종료
        
        // 윈도우의 새로운 끝점 문자에 따라 카운트 증가
        when (dna[end]) {
            'A' -> sa++
            'C' -> sc++
            'G' -> sg++
            'T' -> st++
        }
    }
    // 조건을 만족하는 윈도우의 총 개수 출력
    println(cnt)
}

스택

fun main() = with(System.`in`.bufferedReader()) {
    val stack = ArrayDeque<Int>()
    // 스택에 추가할 다음 정수를 추적하기 위한 변수입니다.
    var next = 1
    // N은 수열의 길이를 나타냅니다.
    val N = readLine().toInt()
    // N개의 정수를 읽어들여 goals 리스트를 구성합니다.
    val goals = List(N) { readLine().toInt() }
    // 결과를 저장할 StringBuilder를 초기화
    val output = StringBuilder()
    
    // goals 리스트의 각 요소에 대해 반복합니다.
    for (goal in goals) {
        // 현재 목표 숫자(goal)가 스택에 넣을 다음 숫자(next)보다 크거나 같은 동안 반복합니다.
        while (goal >= next) {
            // 스택에 next 값을 추가합니다. (스택에 push)
            stack.addLast(next++)
            // '+' 연산을 output에 추가합니다.
            output.append("+\n")
        }
        // 스택의 맨 위 요소가 현재 목표 숫자와 같은 경우 (스택에서 peek)
        if (stack.last() == goal) {
            // 스택에서 해당 요소를 제거합니다. (스택에서 pop)
            stack.removeLast()
            // '-' 연산을 output에 추가합니다.
            output.append("-\n")
        } else {
            // 스택의 맨 위 요소가 목표 숫자와 다르면 "NO"를 출력하고 프로그램을 종료합니다.
            println("NO")
            return
        }
    }
    
    print(output)
}

큐

fun main() = System.`in`.bufferedReader().run {
    val N = readLine().toInt()

    // 입력받은 숫자 범위(1부터 N까지)로 리스트를 생성하고, 이 리스트를 ArrayDeque에 넣어 초기화합니다.
    val queue = ArrayDeque<Int>((1..N).toList())

    while (queue.size > 1) {
        // 첫 번째 요소를 제거합니다.
        queue.removeFirst()
        // 제거된 첫 번째 요소 다음에 오던 요소를 맨 뒤로 옮깁니다.
        queue.addLast(queue.removeFirst())
    }
    // 마지막으로 남은 요소를 출력합니다.
    println(queue.first())
}

우선순위큐

import java.util.PriorityQueue
import kotlin.math.abs

fun main() = System.`in`.bufferedReader().run {
    // 1. 절대값이 작은 순서 
    // 2. 절대값이 같을 경우, 실제 값이 작은 순서
    val pQueue = PriorityQueue(compareBy<Int> { abs(it) }.thenBy { it })

    repeat(readLine().toInt()) {
        val v = readLine().toInt()
        // v가 0이 아니면, 해당 값을 우선순위 큐에 추가합니다.
        if (v != 0) pQueue.add(v) 
        // v가 0이면, 우선순위 큐에서 가장 우선순위가 높은 값을 꺼내 출력합니다.
        // 만약 큐가 비어있다면(꺼낼 요소가 없다면), 0을 출력합니다.
        else println(pQueue.poll() ?: 0)
    }
}

코틀린 기본 정렬

class Solution {
    fun solution(my_string: String): IntArray {
        // 주어진 문자열에서 숫자만 필터링하여 추출하고, 각 숫자를 정수로 변환한 후 정렬하여 반환
        return my_string.filter { Character.isDigit(it) } // 주어진 문자열에서 숫자만 필터링하여 추출
            .map { it.digitToInt() } // 각 문자를 정수로 변환하여 리스트에 담음
            .sorted() // 숫자를 오름차순으로 정렬
            .toIntArray() // 정렬된 숫자들을 포함한 정수 배열로 반환
    }
}

버블정렬

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    // 입력을 한 번에 받고, 배열로 변환
    var A = List(N) { readLine().toInt() }.toTypedArray()
    
    for(i in 0 until N-1) {
        for(j in 0 until (N-1-i)) {
            if(A[j] > A[j+1]) {
            	// 구조 분해 할당을 사용하여 값을 교환
                A[j] = A[j+1].also { A[j+1] = A[j] }
            }
        }
    }
    println(A.joinToString(" "))
}

선택정렬

fun main() = System.`in`.bufferedReader().run {
    val str = readLine() // 숫자를 문자열로 입력받음
    val A = str.map { it.toString().toInt() }.toMutableList() // 각 자리수를 정수로 변환하여 리스트에 저장
    
    for (i in 0 until A.size - 1) {
        var Max = i
        for (j in i + 1 until A.size) {
            if (A[j] > A[Max]) {
                Max = j
            }
        }
        if (i != Max) {
            A[i] = A[Max].also { A[Max] = A[i] }
        }
    }
    println(A.joinToString(""))
}

삽입정렬

fun main() = System.`in`.bufferedReader().run {
    val str = readLine()
    val A = str.map { it.toString().toInt() }.toMutableList()
    
    for(i in 1 until A.size) {
        var index = i
        while(index > 0 && A[index-1] > A[index]) {
            A[index] = A[index-1].also { A[index-1] = A[index] }
            index--
        }
    }
    println(A.joinToString(""))
}

퀵정렬

fun main() = System.`in`.bufferedReader().run {
    val str = readLine()
    val A = str.map { it.toString().toInt() }.toMutableList()

    quickSort(A, 0, A.size - 1)
    
    println(A.joinToString(""))
}

// 퀵 정렬 함수: 배열을 정렬하는 주요 함수
fun quickSort(arr: MutableList<Int>, low: Int, high: Int) {
    // 재귀 정렬의 기저 조건
    if (low < high) {
        // 분할: 피벗을 기준으로 배열을 두 부분으로 나눔
        val pi = partition(arr, low, high)

        // 왼쪽 부분 배열 정렬
        quickSort(arr, low, pi - 1)
        // 오른쪽 부분 배열 정렬
        quickSort(arr, pi + 1, high)
    }
}

// 분할 함수: 배열을 피벗을 기준으로 두 부분으로 나눔
fun partition(arr: MutableList<Int>, low: Int, high: Int): Int {
    // 피벗 선택 (여기서는 마지막 요소)
    val pivot = arr[high]
    // 피벗보다 작은 요소의 인덱스
    var i = (low - 1)
    
    // 현재 요소가 피벗보다 작으면 i를 증가시키고 요소를 교환
    for (j in low until high) {
        if (arr[j] < pivot) {
            i++
            // swap arr[i] and arr[j]
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    
    // 피벗을 올바른 위치로 교환
    // swap arr[i+1] and arr[high] (or pivot)
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    
    // 피벗의 최종 위치 반환
    return i + 1
}

class Solution {
    fun IntArray.quickSort(): IntArray {
        fun partition(low: Int, high: Int): Int {
            // 피벗 선택 (중간값)
            val pivot = this[(low + high) / 2]
            var i = low
            var j = high
            // 피벗을 기준으로 좌우로 나누기
            while (true) {
                // 피벗보다 작은 값이 나올 때까지 i를 증가
                while (this[i] < pivot) i++
                // 피벗보다 큰 값이 나올 때까지 j를 감소
                while (this[j] > pivot) j--
                // i가 j보다 크거나 같으면 종료
                if (i >= j) return j
                // i번째 값과 j번째 값을 교환
                this[i] = this[j].also { this[j] = this[i] }
                i++
                j--
            }
        }

        fun sort(low: Int, high: Int) {
            // low가 high보다 작을 때까지
            if (low < high) {
                val p = partition(low, high)
                sort(low, p)
                sort(p + 1, high)
            }
        }
        sort(0, lastIndex)
        return this
    }

    fun sortArray(nums: IntArray): IntArray {
        return nums.quickSort()
    }
}

병합정렬

fun main() = System.`in`.bufferedReader().run {
    val str = readLine()
    val A = str.map { it.toString().toInt() }.toMutableList()

    mergeSort(A, 0, A.size - 1)
    println(A.joinToString(""))
}

fun mergeSort(arr: MutableList<Int>, left: Int, right: Int) {
    if (left < right) {
        // 중간 지점을 찾아 배열을 나눕니다.
        val middle = left + (right - left) / 2

        // 각 부분 배열을 재귀적으로 정렬합니다.
        mergeSort(arr, left, middle)
        mergeSort(arr, middle + 1, right)

        // 정렬된 부분 배열을 합칩니다.
        merge(arr, left, middle, right)
    }
}

fun merge(arr: MutableList<Int>, left: Int, middle: Int, right: Int) {
    // 왼쪽과 오른쪽 부분 배열의 크기를 계산합니다.
    val n1 = middle - left + 1
    val n2 = right - middle

    // 임시 배열을 생성합니다.
    val L = MutableList(n1) { 0 }
    val R = MutableList(n2) { 0 }

    // 데이터를 임시 배열에 복사합니다.
    for (i in 0 until n1) L[i] = arr[left + i]
    for (j in 0 until n2) R[j] = arr[middle + 1 + j]

    // 임시 배열을 병합하여 arr[]에 복사합니다.
    var i = 0
    var j = 0

    // 초기 인덱스 k를 설정합니다.
    var k = left
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i]
            i++
        } else {
            arr[k] = R[j]
            j++
        }
        k++
    }

    // L[]의 남은 요소를 복사합니다.
    while (i < n1) {
        arr[k] = L[i]
        i++
        k++
    }

    // R[]의 남은 요소를 복사합니다.
    while (j < n2) {
        arr[k] = R[j]
        j++
        k++
    }
}

깊이우선탐색(DFS)

fun main() = System.`in`.bufferedReader().run {
    // 첫 번째 줄에서 n(노드 수)과 m(간선 수)을 읽어 정수로 변환합니다.
    val (n, m) = readLine().split(" ").map { it.toInt() }
    // 방문한 노드를 기록하기 위한 Boolean 배열을 초기화합니다. 인덱스 0은 사용하지 않기 위해 n+1로 설정합니다.
    val visited = BooleanArray(n + 1)
    // 그래프를 표현하기 위한 인접 리스트를 초기화합니다. 각 노드별로 연결된 노드를 저장할 리스트를 포함합니다.
    val graph = List(n + 1) { mutableListOf<Int>() }

    // m개의 간선 정보를 입력받습니다.
    repeat(m) {
        // 간선의 양 끝점을 읽어 정수로 변환하고, 양방향으로 인접 리스트에 추가합니다.
        readLine().split(" ").map { it.toInt() }.let { (s, e) ->
            graph[s].add(e)
            graph[e].add(s)
        }
    }

    // 깊이 우선 탐색(DFS)을 수행하는 함수를 정의합니다.
    fun dfs(v: Int) {
        // 이미 방문한 노드라면 함수를 종료합니다.
        if (visited[v]) return
        // 현재 노드를 방문 처리합니다.
        visited[v] = true
        // 현재 노드와 연결된 모든 노드에 대해 방문하지 않았다면 재귀적으로 DFS를 수행합니다.
        graph[v].forEach { if (!visited[it]) dfs(it) }
    }

    // 연결 요소의 수를 세기 위해 1부터 n까지의 노드에 대해 방문하지 않은 노드가 있다면 DFS를 호출하고, 
    // 결과적으로 true를 반환하여 count 연산을 합니다.
    val count = (1..n).count { i ->
        if (!visited[i]) {
            dfs(i)
            true
        } else false
    }

    println(count)
}

너비우선탐색(BFS)

fun main() = System.`in`.bufferedReader().run {
    // 첫 번째 줄에서 R(행의 수)과 C(열의 수)를 읽어들입니다.
    val (R, C) = readLine().split(" ").map { it.toInt() }
    // 미로를 2차원 List로 읽어들입니다. 각 칸은 문자열에서 정수로 변환됩니다.
    val maze = List(R) { readLine().map { it.toString().toInt() } }

    // 방문 여부 및 거리를 저장할 2차원 List를 초기화합니다. 모든 값은 0으로 시작합니다.
    val visit = List(R) { MutableList(C) { 0 } }
    // 이동할 수 있는 4가지 방향을 정의합니다. (우, 하, 좌, 상)
    val directions = listOf(Pair(0, 1), Pair(1, 0), Pair(0, -1), Pair(-1, 0))
    // BFS를 위한 큐를 초기화하고, 시작점인 (0, 0)을 추가합니다.
    val queue = ArrayDeque<Pair<Int, Int>>().apply { add(Pair(0, 0)) }
    // 시작점을 방문했다고 표시하고, 시작점의 거리 값을 1로 설정합니다.
    visit[0][0] = 1

    while (queue.isNotEmpty()) {
        // 현재 위치를 큐에서 꺼냅니다.
        val (curR, curC) = queue.removeFirst()

        // 정의된 4가지 방향에 대해 반복합니다.
        for ((dr, dc) in directions) {
            val newR = curR + dr
            val newC = curC + dc
            // 새로운 위치가 미로 내부에 있고, 아직 방문하지 않았으며, 이동할 수 있는 칸(1)인 경우
            if (newR in 0 until R && newC in 0 until C && maze[newR][newC] == 1 && visit[newR][newC] == 0) {
                // 새 위치를 큐에 추가합니다.
                queue.add(Pair(newR, newC))
                // 새 위치까지의 거리를 현재 위치의 거리에 1을 더해 갱신합니다.
                visit[newR][newC] = visit[curR][curC] + 1
            }
        }
    }

    // 목적지인 (R-1, C-1)까지의 최소 거리를 출력합니다.
    println(visit[R - 1][C - 1])
}

백트래킹

fun backtrack(uniqueSubs: List<String>, currentSub: String, index: Int) {
	// 문자열의 끝에 도달한 경우
    if (index == s.length) {
    	// 현재 부분 문자열이 비어있지 않으면 maxUniqueCount 갱신
        if (currentSub.isEmpty()) maxUniqueCount = maxOf(maxUniqueCount, uniqueSubs.size)
    	return
    }

    // 현재 문자 추가
    val newSub = currentSub + s[index]

	// 새로 만든 부분 문자열이 고유한 경우
    if (!uniqueSubs.contains(newSub)) {
    	// 고유 부분 문자열 목록에 추가하고 다음 문자로 진행
    	backtrack(uniqueSubs + newSub, "", index + 1)
    }
    // 현재 부분 문자열을 계속 확장하여 다음 문자로 진행
	backtrack(uniqueSubs, newSub, index + 1)
}

코틀린 이진탐색

fun main() = System.`in`.bufferedReader().run {
    readLine() // N, 첫 번째 줄의 입력값은 이후에 사용하지 않으므로 읽기만 함
    val A = readLine().split(" ").map { it.toInt() }.sorted()
    readLine() // M, 세 번째 줄의 입력값도 마찬가지로 읽기만 함
    val targets = readLine().split(" ").map { it.toInt() }

    targets.forEach { target ->
        // binarySearch는 찾은 경우 해당 인덱스(0 이상), 찾지 못한 경우 음수 값을 반환합니다.
        // 따라서 반환값이 0 이상이면 요소가 존재한다는 의미입니다.
        println(if (A.binarySearch(target) >= 0) 1 else 0)
    }
}

이진탐색 구현

fun main() = System.`in`.bufferedReader().run {
    readLine() // 첫 번째 줄(N) 읽기. 배열의 크기이지만 여기선 사용하지 않음
    val A = readLine().split(" ").map { it.toInt() }.sorted() // 정수 배열 A 입력 받고 정렬
    readLine() // 세 번째 줄(M) 읽기. 타겟 숫자의 개수이지만 여기선 사용하지 않음
    val targets = readLine().split(" ").map { it.toInt() } // 타겟 숫자들을 입력 받음

    // 타겟 숫자들에 대해 이진 탐색 실행 후 결과를 문자열로 변환하여 출력
    val result = targets.map { target ->
        binarySearch(A, target) // 타겟 숫자마다 이진 탐색 실행
    }.joinToString("\n") // 결과를 줄바꿈 문자로 구분하여 하나의 문자열로 병합

    println(result) // 최종 결과 출력
}

// 이진 탐색 함수: 주어진 정렬된 리스트와 키(타겟 숫자)를 받아 존재 여부 확인
fun binarySearch(list: List<Int>, key: Int): Int {
    var start = 0 // 탐색 시작점
    var end = list.size - 1 // 탐색 종료점

    while (start <= end) { // 시작점이 종료점보다 작거나 같을 때까지 반복
        val mid = start + (end - start) / 2 // 중간점 계산
        when { // 중간점의 값과 키를 비교
            list[mid] < key -> start = mid + 1 // 키가 더 크면, 탐색 범위를 오른쪽 절반으로 좁힘
            list[mid] > key -> end = mid - 1 // 키가 더 작으면, 탐색 범위를 왼쪽 절반으로 좁힘
            else -> return 1 // 키를 찾은 경우, 1 반환
        }
    }
    return 0 // 루프를 벗어난 경우, 키가 리스트에 없는 것이므로 0 반환
}

그리디 알고리즘

fun main() = System.`in`.bufferedReader().run {
  // 가지고 있는 동전(N)과 만들어야할 금액(K)를 입력받음
  val (N, K) = readLine().split(" ").map { it.toInt() }
  // N개의 줄에 걸쳐 각 동전의 가치를 읽어서 리스트 A에 저장
  val A = List(N) { readLine().toInt() }
    
  // 남은 금액을 K로 초기화
  var remaining = K
  // 리스트 A를 오른쪽(끝)부터 왼쪽(시작)으로 fold 연산을 수행하면서 동전 개수를 세는 과정
  val count = A.foldRight(0) { coin, acc ->
      // 현재 동전의 가치가 남은 금액보다 작거나 같은 경우
      if (coin <= remaining) {
          // 현재 동전으로 만들 수 있는 최대 개수 계산
          val needed = remaining / coin
          // 남은 금액을 현재 동전으로 나눈 나머지로 업데이트
          remaining %= coin
          // 누적된 동전의 개수에 현재 동전으로 만들 수 있는 개수를 더함
          acc + needed
      } else acc // 현재 동전의 가치가 남은 금액보다 큰 경우, 누적값 변경 없이 계속
  }
  
  // 최종적으로 필요한 동전의 최소 개수 출력
  println(count)
}

fun main() = System.`in`.bufferedReader().run {
    // 입력된 문자열을 '-'를 기준으로 분리하여 str 변수에 저장
    val str = readLine().split("-")
    // str의 첫 번째 요소(첫 번째 '-' 이전의 숫자들)를 '+'로 분리한 뒤 각각을 정수로 변환하여 합계를 구함
    // 이 합계를 초기 최소값(min)으로 설정
    var min = str[0].split("+").sumOf { it.toInt() }

    // str의 두 번째 요소부터 마지막 요소까지 반복
    for (i in 1 until str.size) {
        // 각 요소를 '+'로 분리한 뒤 각각을 정수로 변환하여 합계를 구하고
        // 이 합계를 min에서 뺌 (즉, 첫 번째 요소의 합에서 나머지 요소들의 합을 빼는 과정)
        min -= str[i].split("+").sumOf { it.toInt() }
    }

    // 최종 계산된 min 값을 출력
    println(min)
}

소수구하기 (에라토스테네스의 체)

fun main() = System.`in`.bufferedReader().run {
    // 소수 찾을 범위를 입력받습니다 M~N
    val (M, N) = readLine().split(" ").map { it.toInt() }
    // 소수 판별을 위한 Boolean 배열을 초기화합니다. 모든 값을 true로 설정하고, 0과 1은 소수가 아니므로 false로 설정합니다.
    val prime = BooleanArray(N + 1) { it > 1 }

    // 에라토스테네스의 체 알고리즘을 사용하여 소수를 찾습니다.
    for (i in 2..sqrt(N.toDouble()).toInt()) {
        // 현재 숫자 i가 소수가 아닌 경우, 다음 숫자로 넘어갑니다.
        if (!prime[i]) continue
         // i의 배수를 찾아 소수가 아니라고 표시합니다. i*i부터 시작하여 N까지 i씩 증가시키며 반복합니다.
        for (j in i * i..N step i) prime[j] = false
    }
    
    // M부터 N까지의 숫자 중 소수를 출력합니다.
    (M..N).forEach { if (prime[it]) println(it) }
}

최대공약수 최대공배수

class Solution {
    // 두 정수 n과 m을 입력받아 최대공약수와 최소공배수를 계산하는 함수
    fun solution(n: Int, m: Int): IntArray {
        // 두 수의 최대공약수를 계산합니다.
        val gcd = gcd(n, m)

        // 계산된 최대공약수와 최소공배수를 배열로 반환합니다.
        // 최소공배수는 두 수의 곱을 최대공약수로 나눈 값입니다.
        return intArrayOf(gcd, n * m / gcd)
    }

    // 꼬리 재귀를 사용하여 최대공약수를 계산하는 함수
    // 꼬리 재귀 최적화를 통해 컴파일러가 이를 더 효율적인 루프 구조로 변환할 수 있습니다.
    tailrec fun gcd(a: Int, b: Int): Int = 
        if (b == 0) a // b가 0이면, a가 최대공약수입니다.
        else gcd(b, a % b) // b가 0이 아니면, b와 a를 b로 나눈 나머지를 가지고 재귀 호출합니다.
}

이분 그래프

fun main() = System.`in`.bufferedReader().run {
    // 테스트 케이스의 수를 입력받습니다.
    val testCase = readLine().toInt()
    // 각 테스트 케이스에 대해 반복합니다.
    repeat(testCase) {
        // 정점(V)과 간선(E)의 수를 입력받습니다.
        val (V, E) = readLine().split(" ").map { it.toInt() }
        // 각 정점에 연결된 간선을 저장할 그래프를 생성합니다. 각 정점의 인접 리스트로 구현합니다.
        val graph = List(V + 1) { mutableListOf<Int>() }
        // 각 정점의 방문 여부를 저장할 배열을 생성합니다.
        val visited = BooleanArray(V + 1)
        // 각 정점이 속한 집합을 구분하기 위한 배열을 생성합니다.
        val check = IntArray(V + 1)
        // 그래프가 이분 그래프인지 여부를 저장할 변수입니다. 초기값은 true입니다.
        var isBipartite = true

        // u와 v 사이에 양방향 간선을 추가하는 함수입니다.
        fun addEdge(u: Int, v: Int) {
            graph[u].add(v)
            graph[v].add(u)
        }

        // 깊이 우선 탐색(DFS)을 수행하는 함수입니다. 이분 그래프 판별에 사용됩니다.
        fun dfs(node: Int) {
            visited[node] = true
            for (adj in graph[node]) {
                if (!visited[adj]) {
                    check[adj] = (check[node] + 1) % 2
                    dfs(adj)
                } else if (check[node] == check[adj]) {
                    // 현재 정점과 인접 정점이 같은 집합에 속해있다면 이분 그래프가 아닙니다.
                    isBipartite = false
                    return
                }
            }
        }

        // 간선 정보를 입력받아 그래프에 추가합니다.
        repeat(E) {
            val (u, v) = readLine().split(" ").map { it.toInt() }
            addEdge(u, v)
        }

        // 모든 정점에 대해 방문하지 않았고, 그래프가 여전히 이분 그래프라면 DFS를 수행합니다.
        for (i in 1..V) {
            if (!visited[i] && isBipartite) {
                dfs(i)
            }
        }

        // 이분 그래프 여부에 따라 "YES" 또는 "NO"를 출력합니다.
        println(if (isBipartite) "YES" else "NO")
    }
}

유니온 파인드

fun main() = System.`in`.bufferedReader().run {
    // 첫 번째 줄에서 n(노드의 수), m(연산의 수)을 읽어옵니다.
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }
    // 노드 배열을 초기화합니다. 각 노드의 부모를 자기 자신으로 설정합니다.
    val node = IntArray(n + 1) { it }

    // find 함수: 특정 원소가 속한 집합을 찾습니다.
    fun find(b:Int): Int{
        // 노드의 부모가 자기 자신이라면 해당 노드를 반환합니다.
        if(node[b]==b) return b
        // 그렇지 않다면, 노드의 부모를 찾아 재귀적으로 호출합니다.
        node[b] = find(node[b])
        return node[b]
    }

    // union 함수: 두 원소가 속한 집합을 합칩니다.
    fun union(b:Int, c:Int){
        // 두 노드의 루트 노드를 찾아 한쪽의 부모를 다른 한쪽으로 설정합니다.
        node[find(c)] = find(b)
    }

    // m번의 연산을 반복 수행합니다.
    repeat(m) {
        // 연산의 종류(a), 두 노드 번호(b, c)를 입력으로 받습니다.
        val (a, b, c) = readLine()!!.split(' ').map { it.toInt() }
        when(a) {
            0 -> union(b, c) // 0일 경우, 두 노드를 합칩니다.
            1 -> println(if (find(b) == find(c)) "YES" else "NO") // 1일 경우, 두 노드가 같은 집합에 속하는지 확인합니다.
        }
    }
}

위상정렬

fun main() = System.`in`.bufferedReader().run {
    // N과 M을 입력받음. N은 정점의 개수, M은 간선의 개수.
    val (N, M) = readLine().split(' ').map { it.toInt() }
    // 방향 그래프를 나타내는 인접 리스트
    val graph = List(N + 1) { mutableListOf<Int>() }
    // 각 정점의 진입 차수를 저장하는 배열
    val indegree = IntArray(N + 1)
    
    // M번 반복하여 간선 정보를 입력받고 그래프 및 진입 차수 배열을 갱신
    repeat(M) {
        readLine().split(' ').map { it.toInt() }.also { (S, E) ->
            graph[S].add(E) // S에서 E로 가는 간선 추가
            indegree[E]++ // E의 진입 차수 증가
        }
    }
    
    // 진입 차수가 0인 정점들을 찾아 큐에 추가
    val queue = ArrayDeque<Int>().apply {
        indegree.indices
            .filter { indegree[it] == 0 && it != 0  // 진입 차수가 0인 정점을 필터링
            .forEach { this.addLast(it) } // 해당 정점을 큐에 추가
    }
    
    // 위상 정렬의 결과를 저장할 리스트
    val result = mutableListOf<Int>()
    // 큐가 빌 때까지 반복
    while(queue.isNotEmpty()) {
        val current = queue.removeFirst() // 큐에서 정점을 하나 꺼냄
        result.add(current) // 결과 리스트에 추가
        
        // 현재 정점에서 나가는 간선을 제거하며 진입 차수 갱신
        graph[current].forEach { next ->
            if (--indegree[next] == 0) { // 진입 차수가 0이 되면
                queue.addLast(next) // 해당 정점을 큐에 추가
            }
        }
    }
    
    // 결과 리스트의 크기가 N과 같다면 모든 정점을 방문한 것이므로 결과 출력
    // 그렇지 않다면 사이클이 존재하는 것으로 간주하고 메시지 출력
    if (result.size == N) println(result.joinToString(" "))
    else println("사이클이 존재하여 위상 정렬을 완료할 수 없습니다.")
}

최소신장트리(MST)

class Solution {
    fun solution(n: Int, costs: Array<IntArray>): Int {
        // 비용을 기준으로 간선을 오름차순 정렬합니다.
        val sortedCosts = costs.sortedBy { it[2] }
        // 각 노드의 부모 노드를 자기 자신으로 초기화합니다.
        val parent = IntArray(n) { it }

        // 주어진 노드의 루트 노드를 찾는 함수입니다.
        fun find(u: Int): Int {
            // 루트 노드가 자기 자신이 아니면, 루트 노드를 찾을 때까지 재귀적으로 호출합니다.
            if (u != parent[u]) parent[u] = find(parent[u])
            return parent[u]
        }

        // 두 노드를 연결하는 함수입니다. 이미 같은 트리에 속해있다면 연결하지 않습니다.
        fun union(u: Int, v: Int): Boolean {
            val rootU = find(u)
            val rootV = find(v)
            // 두 노드의 루트 노드가 같다면, 이미 같은 트리에 속해있으므로 연결하지 않습니다.
            if (rootU == rootV) return false
            // 두 노드를 하나의 트리로 합칩니다. 여기서는 rootV를 rootU의 부모로 설정합니다.
            parent[rootU] = rootV
            return true
        }

        // 최소 비용을 계산합니다.
        var answer = 0
        // 정렬된 간선 리스트를 순회하면서
        for ((s, e, c) in sortedCosts) {
            // 두 노드를 연결할 수 있다면(즉, 이미 같은 트리에 속해있지 않다면),
            // 해당 간선의 비용을 더하고 두 노드를 연결합니다.
            if (union(s, e)) {
                answer += c
            }
        }
        // 모든 섬을 최소 비용으로 연결하는데 필요한 비용을 반환합니다.
        return answer
    }
}

이진검색트리

fun main() = System.`in`.bufferedReader().run {
    // 입력을 받아 각 줄을 정수로 변환하여 리스트로 만듦
    val tree = readLines().map { it.toInt() }

    // 변환된 리스트를 사용하여 전위 순회 결과를 후위 순회 결과로 변환하는 함수 호출
    pre2post(tree, 0, tree.size)
}

fun pre2post(tree: List<Int>, start: Int, end: Int) {
    // 시작 인덱스와 끝 인덱스가 같으면 더 이상 처리할 노드가 없으므로 함수 종료
    if (start == end)
        return

    // 현재 서브트리의 루트 노드 값
    val root = tree[start]

    // 루트 노드의 바로 다음 인덱스부터 시작하여 오른쪽 자식 노드의 시작 인덱스를 찾음
    var mid = start + 1
    while (mid < end && tree[mid] < root)
        mid++

    // 왼쪽 서브트리에 대해 재귀적으로 함수 호출
    pre2post(tree, start + 1, mid)
    // 오른쪽 서브트리에 대해 재귀적으로 함수 호출
    pre2post(tree, mid, end)
    
    // 후위 순회 결과에 따라 현재 루트 노드를 처리 (출력)
    println("$root")
}

동적계획법(DP) - 피보나치수열

fun main() = System.`in`.bufferedReader().run {
    val n = readLine()!!.toInt()
    tailrec fun fibo(n: Int , pre:Int, next:Int): Int {
        if (n <= 0) return pre
        return fibo(n - 1, next, pre +next)
    }
    print(fibo(n,0,1))
}

fun climbStairs(n: Int): Int {
	// dp[i] = i번째 계단까지 오르는 방법의 수
    val dp = IntArray(n + 1)
    dp[0] = 1
    dp[1] = 1
    // i번째 계단까지 오르는 방법의 수는 i-1번째 계단까지 오르는 방법의 수와 i-2번째 계단까지 오르는 방법의 수의 합과 같습니다.
    for (i in 2..n) {
    	dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]

}