백엔드 개발자로 성장하기 위해서 코틀린을 배워두면 참 좋다. 괜히 코프링 코프링 하는게 아니다.
어떻게 하면 코틀린과 친해질 수 있을까하고 고민하다가
생각한 것이 코틀린으로 백준 문제를 풀어보면서 계속 감을 익히기!
원래는 C++로만 알고리즘 문제를 푸는데, 풀었던 문제들을 블로그에 계속 반강제로 기록하면서
지속적으로 Kotlin을 다룰 수 있게끔 익숙해지고자 한다.
저번에 코틀린으로 코드를 제출했는데 너무 오래 걸려서,
C++로 바꿔서 풀었더니 바로 맞았습니다 뜨는 거 보고 솔직히 암 걸릴 뻔했지만 이것도 수련의 한 과정
그래도 간편하게 작성할 수 있는 점은 참 좋은거 같다.
백준 18870 좌표 압축
난이도: 실버2
태그: 정렬, 값 / 좌표 압축
풀이 날짜: 2025.04.07
https://www.acmicpc.net/problem/18870
1 <= N <= 1,000,000 이기 때문에 O(N^2)은 시간 초과가 발생하므로 O(NlogN) 이하로 코드를 작성해야 한다.
문제에서 Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다는 조건이 있으므로 아래와 같은 순서로 코드를 작성하였다.
- 입력으로 주어진 수열에서 각 수를 오름차순 정렬한 후 중복을 제거한 수열 생성(sortedArr)
- 원래 수열의 각 원소가 정렬된 배열에서 몇 번째 위치(인덱스)에 해당하는지를 이진 탐색으로 찾기
fun main() {
val br = System.`in`.bufferedReader()
val N = br.readLine()!!.toInt()
val arr = br.readLine()!!.split(" ").map { it.toInt() }
val sortedArr = arr.distinct().sorted()
val sb = StringBuilder()
for (i in 0 until N) {
sb.append(sortedArr.binarySearch(arr[i])).append(" ")
}
print(sb)
}코틀린에서 배운점
- 코틀린은 binarySearch()에서 찾는 원소가 존재한다면 해당 원소의 index를 반환한다.
- 자바와 같이 StringBuilder()를 사용하면 시간을 단축시킬 수 있다.
- sort()와 sorted()의 차이
- sort(): 원본 배열을 오름차순으로 정렬한다.
- sorted(): 오름차순 정렬 후, list를 반환하는데 원본 배열은 그대로 둔다.
백준 16922 로마 숫자 만들기
난이도: 실버3
태그: 백트래킹
풀이 날짜: 2025.04.08
https://www.acmicpc.net/problem/16922
중복되는 sum 값들은 set으로 해결하려 했으나, 시간 초과로 인해 50*20+1 크기를 가지는 불리언 배열을 만들어서 해결 나머지는 전형적인 백트래킹 문제
var N = 0
var ans = 0
val arr = arrayOf(1, 5, 10, 50)
val isUsed = BooleanArray(1001)
fun backtracking(K: Int, idx: Int, sum: Int) {
if (K == N) {
if (isUsed[sum]) return
isUsed[sum] = true
ans++
return
}
for (i in idx until 4) {
backtracking(K + 1, i, sum + arr[i])
}
}
fun main() {
val br = System.`in`.bufferedReader()
N = br.readLine()!!.toInt()
backtracking(0, 0, 0)
println(ans)
}코틀린에서 배운점
- C++에 익숙해서 그런지 int N;과 같이 var N: Int로 전역 변수를 생성하였는데 컴파일 오류가 발생하였다.
- 코틀린은 null safety와 초기화 보장을 중요하게 여긴다는 점을 까먹고 있었다.
- 해결법
- var N = 0으로 선언해놓기
- lateinit 사용하기 (Int에는 사용 불가능)
- var N: Int? = null과 같이 nullable로 선언하고 내부에서 null 처리
- main 함수 내부에서 지역 변수로 선언과 동시에 입력 받고, 함수의 인자로 넘기기
백준 13905 세부
난이도: 골드3
태그: 그리디, 분리 집합, 크루스칼
풀이 날짜: 2025.04.09
https://www.acmicpc.net/problem/13905
그리디하게 접근해서, 간선들을 가중치(k)를 기준으로 내림차순 정렬해주고
내림차순으로 정렬된 간선들 차례대로 각 두 정점들을 Union-Find를 통해 같은 집합으로 만들어준다.
그리고 매번 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 같은 집합에 속해있는지 확인하여
같은 집합에 속해있다면, 순회하고 있는 해당 간선의 가중치를 return하면 된다. (그 다음부터는 볼 필요 없음)
data class Edge(val u: Int, val v: Int, val cost: Int)
lateinit var parent: IntArray
fun getParent(x: Int): Int {
if (parent[x] == x) return x;
return getParent(parent[x]).also { parent[x] = it }
}
fun unionParent(u: Int, v: Int) {
var a = getParent(u)
var b = getParent(v)
if (a < b) parent[b] = a
else parent[a] = b
}
fun findParent(u: Int, v: Int): Boolean {
var a = getParent(u)
var b = getParent(v)
if (a == b) return true
else return false
}
fun main() = with(System.`in`.bufferedReader()) {
val (N, M) = readLine()!!.split(" ").map { it.toInt() }
val (s, e) = readLine()!!.split(" ").map { it.toInt() }
parent = IntArray(N + 1) { it }
val edges = ArrayList<Edge>()
for (i in 0 until M) {
val (u, v, cost) = readLine()!!.trim().split(" ").map { it.toInt() }
edges.add(Edge(u, v, cost))
}
edges.sortByDescending { it.cost }
for ((u, v, cost) in edges) {
unionParent(u, v)
if (findParent(s, e)) {
println(cost)
return
}
}
println(0)
}코틀린에서 배운점
- sortByDescending을 통해 내림차순 정렬시, { it.cost }와 같이 내부 객체의 값을 기준으로 편리하게 정렬 가능
- with 스코프 함수를 활용해 System.`in`.bufferedReader()를 편리하게 사용할 수 있다.
- with()로 감싼 객체 내 컨텍스트 안에서 코드를 실행하게 해줌
- 나중에 초기화할 예정인 변수에 대해서는 lateinit 키워드를 추가해준다
- lateinit var에 기본형(primitive type)을 사용 못하는 이유: https://velog.io/@no1msh1217/Kotlin-lateinit-var%EC%97%90-%EA%B4%80%ED%95%98%EC%97%AC
- also 스코프 함수를 활용해 아래 내용을 간결하게 표현할 수 있다.
val root = getParent(parent[x])
parent[x] = root
return root
백준 1822 차집합
난이도: 실버4
태그: 해시를 사용한 집합과 맵
풀이 날짜: 2025.04.09
https://www.acmicpc.net/problem/1822
집합 A의 원소들을 map에 넣고, 집합 B의 원소들을 삭제해주면 된다. set으로도 쉽게 가능
var value = 0
fun main() = with(System.`in`.bufferedReader()) {
val (A, B) = readLine()!!.split(" ").map { it.toInt() }
val aValues = readLine()!!.split(" ").map { it.toInt() }
val bValues = readLine()!!.split(" ").map { it.toInt() }
val m = mutableMapOf<Int, Boolean>()
aValues.forEach { m[it] = true }
bValues.forEach { m.remove(it) }
println(m.size)
println(m.keys.sorted().joinToString(" "))
}코틀린에서 배운점
- .take(a)
- 리스트에서 앞에서부터 a개 요소만 가져오는 코틀린 컬렉션 함수
- 혹시라도 사용자가 a보다 더 많이 입력했을 경우를 대비해야 한다면
- readln().split(" ").map.take(a)를 사용해주면 유용하다.
- 입력이 명확하게 정해져 있는 알고리즘 문제에서는 해당 경우로 쓸 일이 없을거 같긴하다
- map vs mutableMap
- map은 변경 불가능한 맵(read-only map), mutableMap은 변경 가능한 맵(mutable map)
- 즉, 맵의 내용이 변경되지 않아야 하며 모든 요소가 처음부터 알려져 있는 경우는 map
- 맵의 내용이 실행 도중에 변경될 수 있어야 하는 경우에는 mutableMap 사용
백준 23295 스터디 시간 정하기 1
난이도: 골드3
태그: 누적합, 슬라이딩 윈도우
풀이 날짜: 2025.04.11
https://www.acmicpc.net/problem/23295
스터디의 시작 시간과 종료 시간이 반복해서 입력으로 주어지기 때문에, imos법을 활용하여 시작 시간과 종료 시간만 설정해 준 뒤 T = 100,000 까지의 구간을 누적해준다. 그리고 슬라이딩 윈도우로 입력으로 주어진 T 구간 만큼 살피면서 구간 합이 가장 클 때를 구해주면 된다.
fun main() = with(System.`in`.bufferedReader()) {
val (N, T) = readLine()!!.split(" ").map { it.toInt() }
val psum = IntArray(100_001)
repeat (N) {
val K = readLine()!!.toInt()
repeat(K) {
val (s, e) = readLine()!!.split(" ").map { it.toInt() }
psum[s]++
psum[e]--
}
}
for (i in 1..100_000)
psum[i] += psum[i - 1]
var sum: Long = 0
var ans: Long = 0
var p = Pair(0, 0)
for (i in 0..100_000) {
sum += psum[i]
if (i >= (T - 1)) {
if (ans < sum) {
ans = sum
p = Pair(i - T + 1, i + 1)
}
sum -= psum[i - (T - 1)]
}
}
println("${p.first} ${p.second}")
}코틀린에서 배운점
- 코틀린에도 c++의 pair<int, int>와 같이 두 개의 객체를 반환해야할 때 유용한 Pair 객체가 존재한다
- Pair(1, 2)와 1 to 2와 동일 -> to 키워드를 이용한 Pair 생성
- 3개 이상의 값이 필요할 경우 Triple 객체 사용하기
백준 17612 쇼핑몰
난이도: 골드2
태그: 우선순위 큐, 자료구조
풀이 날짜: 2025.04.13
https://www.acmicpc.net/problem/17612
우선순위 큐를 적용하기 위해 문제에서 제시하는 아래 조건을 유심히 볼 필요가 있다.
- 입장 시: 두 계산대에서 기다려야 할 시간이 같을 경우에는 가장 번호가 작은 계산대로 안내를 한다
- 퇴장 시: 계산을 마친 고객의 시간이 동일하다면 출구에 가까운 높은 번호 계산대의 고객부터 먼저 빠져나간다.
해당 조건으로 인해서 우선순위 큐의 정렬 조건을 끝나는 시간을 기준으로 오름차순하고, 끝나는 시간이 동일하다면 계산대 번호로 오름차순 정렬되도록 구현하였다. 이렇게 되면 입장에 대한 조건은 만족하지만, 퇴장에 대한 조건은 만족하지 않는다.
그렇기 때문에 퇴장할 때는 우선순위 큐(exit)에 계산대 번호(table)의 음수 값을 삽입하여 해결하였다.
즉, 계산대 번호(3, 7)을 exit에 삽입 시 (-7, -3) 순서로 정렬되어 7번부터 빠져나가므로 퇴장 조건에 만족하게 된다.
import java.util.PriorityQueue
data class Info(val w: Int, val table: Int, val id: Long)
fun main() = with(System.`in`.bufferedReader()) {
val (N, K) = readLine()!!.split(" ").map { it.toInt() }
// 끝나는 시간 오름차순, 동일한 시간이라면 계산대 번호 오름차순으로 정렬
val entry = PriorityQueue(compareBy<Info> { it.w }.thenBy { it.table })
val exit = PriorityQueue(compareBy<Info> { it.w }.thenBy { it.table })
// 계산대 개수만큼 미리 초기화
repeat(K) {
entry.add(Info(0, it + 1, 0L))
}
repeat(N) {
val (idStr, wStr) = readLine()!!.split(" ")
val id = idStr.toLong()
val w = wStr.toInt()
val top = entry.poll()
entry.add(Info(w + top.w, top.table, id))
if (top.id > 0) {
exit.add(Info(top.w, -top.table, top.id))
}
}
while (entry.isNotEmpty()) {
val top = entry.poll()
if (top.id > 0) {
exit.add(Info(top.w, -top.table, top.id))
}
}
var tot = 0L
var cnt = 1
while (exit.isNotEmpty()) {
val id = exit.poll().id
tot += (cnt * id)
cnt++
}
println(tot)
}코틀린에서 배운점
- C++과 다르게 Kotlin의 우선순위 큐는 min-heap 방식으로 만들어져 있어서 작은 값이 맨 앞에 온다
- with(System.in.bufferedReader()) 안에서 readln()을 쓰지말기....
- readln()은 내부적으로 전역으로 공유되는 기본 입력 스트림 (System.in)에 연결된 리더만 사용한다.
- with(System.in.bufferedReader()) { ... } 안에서 쓰는 readLine()은 만든 버퍼 리더에서 입력을 받아옴
- 이 둘은 다른 입력 스트림이기 때문에 이로 인해 입력이 꼬이거나, 아무 출력 없이 멈추는 현상이 발생 가능
- with 블록에서 만들어진 입력 스트림은 무시되고, System.in을 다시 열어서 입력을 받으려고 시도하게 된다.
백준 22945 팀 빌딩
난이도: 골드4
태그: 투 포인터
풀이 날짜: 2025.04.16
https://www.acmicpc.net/problem/22945
아래 조건의 최대값을 구해야 하기 때문에 배열의 양 끝에 포인터를 두고 탐색하는 방식으로 구현했다.
- (개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) × min(개발자 A의 능력치, 개발자 B의 능력치)
- 각 개발자의 능력치를 [1, 4, 2, 5]라고 하고, 1과 5가 한 팀을 이룬다면 이 팀의 능력치는 2 x min(1, 5) = 2
fun main() = with(System.`in`.bufferedReader()){
val N = readLine()!!.toInt()
val arr = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
var ans = 0
var st = 0
var en = N - 1
while (st <= en) {
val between = en - st - 1
ans = maxOf(ans, between * minOf(arr[st], arr[en]))
if (arr[en] > arr[st])
st++
else
en--
}
println(ans)
}코틀린에서 배운점
- maxOf/minOf vs max/min
- max/min은 두 값(숫자) 중 더 큰 값을 반환, maxOf/minOf은 여러 값을 동시에 비교
- maxOf/minOf는 숫자뿐만 아니라 Comparable 객체(문자열 등)도 비교 가능
- max/min을 사용하려면 import kotlin.math.* 선언을 해줘야 함, maxOf/minOf는 기본 제공
백준 1431 시리얼 번호
난이도: 실버3
태그: 문자열, 정렬
풀이 날짜: 2025.04.17
https://www.acmicpc.net/problem/1431
문제에서 제시하는 정렬 조건과 우선순위는 다음과 같다.
- 문자열 길이가 짧은 순
- 같다면, 각 문자열에 존재하는 숫자의 합이 작은 순
- 같다면, 문자열 사전순
정렬하기 전에, 각 문자열의 길이와 sumOfDigits라는 별도의 함수를 만들어서 각 문자열에 대한 2번 조건의 합을 구해서 삽입해주었다. 기존에는 sortWith으로 정렬할 때 람다식 안에 sumOfDigits 함수를 넣어주었는데, 이렇게 되면 정렬 과정에서 여러 번 호출될 수 있어 아래 방식으로 수정해 주었다.
val arr = mutableListOf<Triple<String, Int, Int>>()
fun sumOfDigits(input: String): Int {
return input.filter { it.isDigit() }
.map { it - '0' }
.sum()
}
fun main() = with(System.`in`.bufferedReader()) {
val N = readLine()!!.toInt()
repeat(N) {
val str = readLine()!!
arr.add(Triple(str, str.length, sumOfDigits(str)))
}
arr.sortWith(
compareBy<Triple<String, Int, Int>> { it.second }
.thenBy { it.third }
.thenBy { it.first }
)
for ((str, _, _) in arr) {
println(str)
}
}코틀린에서 배운점
- isLetter: 문자인지 확인
- isDigit: 숫자인지 확인
백준 10799 쇠막대기
난이도: 실버2
태그: 스택
풀이 날짜: 2025.04.21
https://www.acmicpc.net/problem/10799
풀이는 짧지만, 풀이 방식을 떠올리는데 애먹었던 문제
문제의 주어진 조건에서 "레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( )’ 으로 표현된다"를 명심하고
문제 접근 방식은 아래와 같다.
( ( ( ) ) ) 와 같은 예시가 있다고 했을 때,
- ( ( 가 등장한 이후에 레이저()가 나왔으므로 결과에 +2
- 레이저 이후에 ) 가 나오면 쇠막대기 끝에 도달했다는 의미이므로 +1 --> 위 예시에서는 )와 )로 총 +2가 수행됨
- 결과적으로 4개의 쇠막대기 조각으로 분리됨
접근 방식을 토대로 예제 입력 1에 대해서 살펴보면 아래와 같다.
그리고 무심코 아래와 같이 str[i - 1] == '('이 아닌, st.top() == '('으로 풀면 안된다.
아래와 같이 스택의 top으로 확인하면 결과값을 과하게 증가시키는(?) 문제가 발생할 수 있음! (내가 이래서 틀림)
else if (str[i] == ')') {
if (st.top() == '(') {
st.pop()
ans += st.size
} else {
st.pop()
ans += 1
}
}예를 들어, ( ( ) ( ) ) 와 같은 입력에서 마지막 ) 를 처리할 때
- str[i - 1] == '('
- 문자열 str에서 바로 직전 문자가 ) 이므로,
- 해당 if문이 아닌 else문에 걸려 쇠막대기의 끝으로 판단하여 ans += 1을 수행
- st.top() == '('
- 현 시점에서 스택의 top은 ( 이므로,
- if문의 코드가 실행되어 ans += st.size 인 스택 사이즈만큼 증가시켜버림
import java.util.Stack
var ans = 0
val st = Stack<Char>()
fun main() = with(System.`in`.bufferedReader()) {
val str = readLine()!!
for (i in 0 until str.length) {
if (str[i] == '(') {
st.push('(')
} else if (str[i] == ')') {
if (str[i - 1] == '(') {
st.pop()
ans += st.size
} else {
st.pop()
ans += 1
}
}
}
println(ans)
}
백준 22868 산책 (small)
난이도: 골드3
태그: 그래프, 너비 우선 탐색
풀이 날짜: 2025.04.26
https://www.acmicpc.net/problem/22868
문제에서 가장 짧은 거리의 경로가 여러개 나올 경우, 나열된 이동 경로(ex. 1 > 4 > 3 > 2) 중에 사전순으로 가장 먼저 오는 것을 선택한다는 조건이 있으므로, 입력 받은 N개의 정점들의 인접리스트들을 오름차순으로 정렬해준다.
또한 방문한 정점을 제외한 다른 정점으로 이동해야된다는 조건이 있으므로 int형의 path 배열을 통해 이전에 들렸던 정점을 기록해준다. 예를 들어 u -> v로 갔다면 path[v] = u
해당 과정을 bfs를 수행할 때마다 기록하므로,
S -> E로 갈 때 기록된 path 배열을 참고하여 E -> S로 bfs를 다시 한번 돌리기 전에
false값으로 초기화된 visited 배열에 path[E]부터 시작해서 방문했었던 정점들을 visited 배열에 true로 다시 기록해준다. (clear 함수 참고)
import java.util.ArrayDeque
import java.util.Queue
const val MAX = 10005
var ans = 0
val adj = Array(MAX) { mutableListOf<Int>() }
val visited = BooleanArray(MAX)
val path = IntArray(MAX)
fun bfs(st: Int, en: Int): Int {
val q: Queue<Pair<Int, Int>> = ArrayDeque()
q.offer(Pair(st, 0))
visited[st] = true
while (q.isNotEmpty()) {
val here = q.peek().first;
val cost = q.peek().second;
q.poll();
for (i in 0 until adj[here].size) {
val there = adj[here][i]
if (!visited[there]) {
visited[there] = true
path[there] = here
q.offer(Pair(there, cost + 1))
}
if (there == en)
return cost + 1
}
}
return 0
}
fun clear(st: Int) {
visited.fill(false)
var k = path[st]
while (true) {
visited[k] = true
k = path[k]
if (k == 0)
break
}
}
fun main() = with(System.`in`.bufferedReader()) {
val (N, M) = readLine()!!.split(" ").map { it.toInt() }
repeat(M) {
val (u, v) = readLine()!!.split(" ").map { it.toInt() }
adj[u].add(v);
adj[v].add(u);
}
for (i in 1..N)
adj[i].sort()
val (S, E) = readLine()!!.split(" ").map { it.toInt() }
ans += bfs(S, E)
clear(E)
ans += bfs(E, S)
println(ans)
}코틀린에서 배운점
- C++에서 배열 초기화시 사용하는 memset과 fill처럼, Kotlin에서도 fill 사용
- C++ : fill(visited, visited + MAX, false)
- Kotlin: visited.fill(false)