프로그래밍

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val mp = HashMap<Int,Int>() // 순서가 필요한 경우 TreeMap 사용

    mp[1]=1 // 데이터 삽입시
    mp[2]=2
    mp[3]=3

    mp[1]=(mp[1]?:0)+1 // 기존 데이터를 이용한 수정시 (예를 들어 1증가) null체크를 위해 엘비스 연산자 사용

    for((key,value) in mp){
        println("key:$key value:$value")
    }
//    출력
//    key:1 value:2
//    key:2 value:2
//    key:3 value:3
}

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val mp = HashMap<Int,Int>() // 순서가 필요한 경우 TreeMap 사용

    mp[1]=1 // 데이터 삽입시
    mp[2]=2
    mp[3]=3

    mp[1]=(mp[1]?:0)+1 // 기존 데이터를 이용한 수정시 (예를 들어 1증가) null체크를 위해 엘비스 연산자 사용

    for((key,value) in mp){
        println("key:$key value:$value")
    }
//    출력
//    key:1 value:2
//    key:2 value:2
//    key:3 value:3
}

코틀린에서 map을 사용하는 예시입니다.

C++처럼 mp[1]++ 이런 연산은 안되고 엘비스 연산자를 이용해

mp[1]=(mp[1]?:0)+1 이렇게 해주어야 하는것이 불편하네요. 

sortWith + 사용자정의 comparator

    var arr1 = mutableListOf(5,4,2,7,1)
    arr1.sortWith{a,b-> b.compareTo(a)} // [7, 5, 4, 2, 1]


    var arr2 = mutableListOf<Pair<Int,Int>>(Pair(1,3),Pair(2,5),Pair(2,4),Pair(6,2))
    arr2.sortWith{ a, b ->
        var k:Int = a.first.compareTo(b.first)
        when(k){
            0 -> a.second.compareTo(b.second)
            else -> k
        }
    } // [(1, 3), (2, 4), (2, 5), (6, 2)]
   
    println(arr1.toString())
    println(arr2.toString())

알고리즘 문제를 풀 때 문제에 따라 사용자 정의 comparator를 전달해서 정렬을 해야하는 경우가 종종 있습니다.

C++에서와 비슷하게 코틀린에서도 컬렉션 sortWith 메소드에 Comparator 구현체를 전달하면 사용자가 원하는 방식으로 정렬을 할 수 있습니다.

Pair도 역시 C++과 비슷한 방식으로 정렬이 가능합니다.

sortWith + compareBy / sortedBy

fun main(){

    var arr1 = mutableListOf<Pair<Int,Int>>(Pair(6,2),Pair(2,5),Pair(2,4),Pair(1,3))
    arr1.sortWith(compareBy({it.first},{it.second}))

    var arr2 = mutableListOf<Pair<Int,Int>>(Pair(6,2),Pair(2,5),Pair(2,4),Pair(1,3))
    var parr2 = arr2.sortedBy{it.second}.sortedBy{it.first}

    println(arr1.toString())  // [(1, 3), (2, 4), (2, 5), (6, 2)]
    println(parr2.toString()) // [(1, 3), (2, 4), (2, 5), (6, 2)]
}

우와 같이 sortWith에 comparator를 return해주는 compareBy를 전달하는 방법도 있습니다.

compareBy({1순위로 비교할 프로퍼티},{2순위로 비교할 프로퍼티}....) 처럼 넣어주면 됩니다.

위 예제에서는 it.frst, it.second를 순서로 전달함으로써 first를 우선으로 비교하고, 같으면 second로 비교해서 오름차순으로 정렬하라는 의미입니다.

sortedBy를 이용하는 방법도 있습니다.

sortedBy{비교할 프로퍼티} 으로 써주면 적어준 프로퍼티 기준으로 오름차순 정렬합니다.

arr2에서 해주는 것과 같이 pair의 second부터 정렬해주고, first를 정렬하면 first를 1순위, second를 2순위로 비교해서 정렬하는 것과 같은 효과입니다.

https://www.acmicpc.net/problem/10971

[난이도] Silver2
[유형] 백트래킹

[풀이]
N제한이 10밖에 안되기 때문에 순회할 수 있는 모든 경우를 백트래킹 해주면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min
import java.util.*
var N=0
val cost = Array(10,{Array(10){0}})
val visit = Array(10){false}
var ans=987654321
fun sol(start:Int,n:Int,sum:Int,cnt:Int){
    visit[n]=true
    //println("n:${n}, sum:${sum}, cnt:${cnt}")
    if(cnt==N && cost[n][start]>0){
        ans=min(ans,sum+cost[n][start])
    }
    for(i in 0 until N){
        if(cost[n][i]>0 && !visit[i]){
            sol(start,i,sum+cost[n][i],cnt+1)
        }
    }
    visit[n]=false
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    N=readLine().toInt()
    for(i in 0 until N){
        var ip = readLine().split(' ').map{it.toInt()}
        for(j in 0 until N) cost[i][j]=ip[j]
    }
    for(i in 0 until N) {
        sol(i,i, 0, 1)
    }
    println(ans)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/10971.cpp

https://www.acmicpc.net/problem/4963

[난이도] Silver2
[유형] DFS

[풀이]
간단한 DFS 문제

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
val mxN = 250000
var Primes = Array(mxN+1){true}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    for(i in 2..mxN/2){
        if(!Primes[i]) continue
        for(j in i*2..mxN step i) Primes[j] = false
    }
    while(true){
        var k=readLine().toInt()
        if(k==0) break
        var ans = 0
        for(i in k+1..2*k) if(Primes[i]) ans++
        println(ans)
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/4963.cpp

https://www.acmicpc.net/problem/4948

[난이도] Silver2
[유형] 에라토스테네스의 체

[풀이]
에라토스테네스의 체

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
val mxN = 250000
var Primes = Array(mxN+1){true}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    for(i in 2..mxN/2){
        if(!Primes[i]) continue
        for(j in i*2..mxN step i) Primes[j] = false
    }
    while(true){
        var k=readLine().toInt()
        if(k==0) break
        var ans = 0
        for(i in k+1..2*k) if(Primes[i]) ans++
        println(ans)
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/4948.cpp

https://www.acmicpc.net/problem/15990

[난이도] Silver3
[유형] DP

[풀이]
DP[i][j] : 가장 마지막에 더한 숫자가 i이며 j를 만들 수 있는 방법의 수.

위와 같이 마지막에 더한 수 i를 기록할 수 있는 2차원 테이블을 만들어서 풀 수 있다.

import java.io.BufferedReader
import java.io.InputStreamReader
val mod = 1e9.toInt()+9
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var t = readLine().toInt()
    val dp = Array<IntArray>(4) { IntArray(100001) }
    dp[1][1]=1
    dp[2][2]=1
    dp[3][3]=1
    for(i in 1..100000){
        for(j in 1..3){
            if(i-j<0) continue
            for(k in 1..3){
                if(j!=k)
                    dp[j][i]=(dp[j][i]+dp[k][i-j])%mod
            }
        }
    }
    while(t-->0){
        val N = readLine().toInt()
        println(((dp[1][N]+dp[2][N])%mod+dp[3][N])%mod)
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/15990.cpp

https://www.acmicpc.net/problem/1373

[난이도] Bronze2
[유형] 수학

[풀이]
2진수 문자열을 3개씩 나눠서 3개를 8진수의 한자리로 보고 변환해주면 0~7의 수로 바꿀 수 있다.

import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine()
    n = n.reversed()
    val arr = listOf(1,2,4)
    var ans=StringBuilder()
    for(i in n.indices step 3){
        var t=0
        for(j in 0..2){
            if(i+j>=n.length) break
            t+=arr[j]*(n[i+j]-'0')
        }
        ans.append(t.toString())
    }
    println(ans.reverse())
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Bronze2/1373.cpp

https://www.acmicpc.net/problem/17087

[난이도] Silver1
[유형] 수학

[풀이]
수빈이의 위치와 동생들의 위치의 차이를 배열에 넣어놓고
유클리드 호제법을 이용해 모든 값에 대한 최대공약수를 구하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.*
fun gcd(n:Int,m:Int):Int{
    var a=n
    var b=m
    if(a>b) a=b.also{b=a}

    while(a>0){
        var c = b%a
        b=a
        a=c
    }
    return b
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val ip = readLine().split(' ')
    val N = ip[0].toInt()
    val S = ip[1].toInt()
    val arr = readLine().split(' ').map { abs(S-it.toInt()) }
    var prev=arr[0]
    for(a in arr) prev=gcd(a,prev)
    println(prev)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/17087.cpp