코틀린으로 하는 경쟁 프로그래밍
코틀린으로 하는 경쟁 프로그래밍
이 튜토리얼은 두 부류의 독자를 모두 겨냥해서 만들어졌어요. 코틀린을 써 본 적 없는 경쟁 프로그래머, 그리고 경쟁 프로그래밍 대회에 참가해 본 적 없는 코틀린 개발자, 둘 다를 위한 글이에요. 두 경우 모두 기본적인 프로그래밍 실력은 갖추고 있다고 가정할게요.
경쟁 프로그래밍(Competitive programming)은 엄격한 제약 안에서 정확하게 명세된 알고리즘 문제를 푸는 프로그램을 작성하는 일종의 두뇌 스포츠예요. 문제는 어떤 소프트웨어 개발자라도 풀 수 있고 올바른 답을 내는 데 코드가 거의 필요 없는 단순한 것에서부터, 특별한 알고리즘과 자료구조에 대한 지식, 그리고 많은 연습을 요구하는 복잡한 것까지 다양해요. 코틀린은 원래 경쟁 프로그래밍을 위해 만들어진 언어는 아니지만 우연찮게 이 분야에 아주 잘 맞아요. 프로그래머가 코드를 작성하고 읽을 때 필요한 전형적인 보일러플레이트를 동적 타입 스크립트 언어 수준에 가깝게 줄여 주면서도, 정적 타입 언어의 도구와 성능은 그대로 제공하거든요.
IntelliJ IDEA에서 코틀린 프로젝트를 만드는 방법에 대해 더 자세히 알고 싶다면 콘솔 앱 만들기(Create a console app) 튜토리얼을 참고하세요. 경쟁 프로그래밍에서는 보통 프로젝트를 하나 만들고, 각 문제의 해답을 단일 소스 파일에 작성해요.
간단한 예제: Reachable Numbers 문제
구체적인 예시를 하나 볼게요.
Codeforces Round 555는 4월 26일에 3부 디비전(3rd Division)을 대상으로 열렸어요. 즉 어떤 개발자라도 도전해 볼 만한 문제들로 구성됐다는 뜻이죠. 이 링크로 문제를 읽어 볼 수 있어요. 그중 가장 간단한 문제가 Problem A: Reachable Numbers예요. 문제에서 서술된 단순한 알고리즘을 그대로 구현하라는 내용이죠.
해결을 시작하려면 먼저 이름을 아무렇게나 정한 코틀린 소스 파일을 만들어요. A.kt면 충분해요. 먼저 문제에서 다음과 같이 정의한 함수를 구현해야 해요.
함수 f(x)를 이렇게 정의해요. x에 1을 더한 다음, 결과 숫자에 끝자리 0(trailing zero)이 하나라도 있는 동안 그 0을 제거해요.
코틀린은 실용적이고 특정 사상을 강요하지 않는(opinionated하지 않은) 언어로, 명령형 스타일과 함수형 스타일을 모두 지원하면서 개발자를 어느 한쪽으로 밀어붙이지 않아요. f 함수를 꼬리 재귀(tail recursion) 같은 코틀린 기능을 활용해 함수형 스타일로 구현할 수 있어요.
tailrec fun removeZeroes(x: Int): Int =
if (x % 10 == 0) removeZeroes(x / 10) else x
fun f(x: Int) = removeZeroes(x + 1)
혹은 전통적인 while 루프와 코틀린에서 var로 표현하는 가변 변수를 써서 f 함수를 명령형으로 구현할 수도 있어요.
fun f(x: Int): Int {
var cur = x + 1
while (cur % 10 == 0) cur /= 10
return cur
}
코틀린은 타입 추론(type-inference)이 널리 쓰여 많은 곳에서 타입을 생략할 수 있어요. 그래도 모든 선언은 여전히 컴파일 시점에 정해지는 명확한 정적 타입을 가져요.
이제 남은 건 입력을 읽고, 문제가 요구하는 나머지 알고리즘——표준 입력으로 주어지는 초기 숫자 n에 함수 f를 반복 적용하면서 만들어지는 서로 다른 정수의 개수를 세는 것——을 구현하는 main 함수를 작성하는 일이에요.
기본적으로 코틀린은 JVM 위에서 동작하며, 풍부하고 효율적인 컬렉션 라이브러리에 직접 접근할 수 있어요. 동적 크기 배열(ArrayList), 해시 기반 맵과 집합(HashMap/HashSet), 트리 기반의 정렬된 맵과 집합(TreeMap/TreeSet) 같은 범용 컬렉션과 자료구조가 준비돼 있죠. 함수 f를 적용하면서 이미 도달한 값을 추적하는 데 정수 해시 집합을 쓰면, 문제에 대한 직관적인 명령형 해법을 아래처럼 작성할 수 있어요.
fun main() {
var n = readln().toInt() // read integer from the input
val reached = HashSet<Int>() // a mutable hash set
while (reached.add(n)) n = f(n) // iterate function f
println(reached.size) // print answer to the output
}
경쟁 프로그래밍에선 잘못된 형식의 입력을 처리할 필요가 없어요. 입력 형식은 항상 정확하게 명세되고, 실제 입력은 문제 서술의 입력 명세에서 벗어날 수 없거든요. 그래서 코틀린의 readln() 함수를 쓸 수 있어요. 이 함수는 입력 문자열이 존재함을 단언(assert)하고, 그렇지 않으면 예외를 던져요. 마찬가지로 String.toInt() 함수도 입력 문자열이 정수가 아니면 예외를 던져요.
fun main() {
var n = readLine()!!.toInt() // read integer from the input
val reached = HashSet<Int>() // a mutable hash set
while (reached.add(n)) n = f(n) // iterate function f
println(reached.size) // print answer to the output
}
readLine() 함수 호출 뒤에 코틀린의 null-단언 연산자 !!가 쓰인 점에 주목해 보세요. 코틀린의 readLine() 함수는 nullable 타입 String?을 반환하도록 정의돼 있고, 입력이 끝나면 null을 반환해요. 그래서 개발자가 입력이 없는 경우를 명시적으로 처리하도록 강제하죠.
경쟁 프로그래밍에선 잘못된 형식의 입력을 처리할 필요가 없어요. 입력 형식은 항상 정확하게 명세되고, 실제 입력은 문제 서술의 입력 명세에서 벗어날 수 없어요. null-단언 연산자 !!가 하는 일이 바로 그것이에요——입력 문자열이 존재함을 단언하고, 그렇지 않으면 예외를 던지죠. String.toInt()도 마찬가지예요.
모든 온라인 경쟁 프로그래밍 대회는 미리 작성된 코드를 쓸 수 있게 허용해요. 그래서 경쟁 프로그래밍에 맞춘 유틸리티 함수로 나만의 라이브러리를 정의해서, 실제 해법 코드를 읽고 쓰기 조금 더 쉽게 만들 수 있어요. 그러면 이 코드를 해법의 템플릿으로 사용하게 돼요. 예를 들어 경쟁 프로그래밍에서 입력을 읽는 다음과 같은 헬퍼 함수를 정의할 수 있어요.
private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutions
private fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutions
여기서 private 가시성 수정자(visibility modifier)가 쓰인 점을 눈여겨보세요. 가시성 수정자의 개념은 경쟁 프로그래밍과는 전혀 무관하지만, 이걸 쓰면 같은 템플릿을 바탕으로 여러 해법 파일을 만들어도 같은 패키지 안의 공개(public) 선언이 충돌한다는 오류 없이 배치할 수 있어요.
함수형 연산자 예제: Long Number 문제
더 복잡한 문제에는 코틀린의 방대한 컬렉션 함수형 연산 라이브러리가 유용해요. 보일러플레이트를 최소화하고 코드를 위에서 아래로, 왼쪽에서 오른쪽으로 흐르는 일관된 데이터 변환 파이프라인으로 바꿔 주거든요. 예를 들어 Problem B: Long Number 문제는 단순한 탐욕 알고리즘(greedy algorithm)을 구현하면 되는데, 이 스타일로 가변 변수 하나 없이도 작성할 수 있어요.
fun main() {
// read input
val n = readln().toInt()
val s = readln()
val fl = readln().split(" ").map { it.toInt() }
// define local function f
fun f(c: Char) = '0' + fl[c - '1']
// greedily find first and last indices
val i = s.indexOfFirst { c -> f(c) > c }
.takeIf { it >= 0 } ?: s.length
val j = s.withIndex().indexOfFirst { (j, c) -> j > i && f(c) < c }
.takeIf { it >= 0 } ?: s.length
// compose and write the answer
val ans =
s.substring(0, i) +
s.substring(i, j).map { c -> f(c) }.joinToString("") +
s.substring(j)
println(ans)
}
fun main() {
// read input
val n = readLine()!!.toInt()
val s = readLine()!!
val fl = readLine()!!.split(" ").map { it.toInt() }
// define local function f
fun f(c: Char) = '0' + fl[c - '1']
// greedily find first and last indices
val i = s.indexOfFirst { c -> f(c) > c }
.takeIf { it >= 0 } ?: s.length
val j = s.withIndex().indexOfFirst { (j, c) -> j > i && f(c) < c }
.takeIf { it >= 0 } ?: s.length
// compose and write the answer
val ans =
s.substring(0, i) +
s.substring(i, j).map { c -> f(c) }.joinToString("") +
s.substring(j)
println(ans)
}
이 빽빽한 코드에서는 컬렉션 변환 외에도 로컬 함수(local function)와 elvis 연산자 ?: 같은 편리한 코틀린 기능을 볼 수 있어요. 이 둘을 쓰면 "값이 양수면 그 값을 쓰고, 아니면 길이를 쓰기" 같은 관용구를 .takeIf { it >= 0 } ?: s.length 같은 간결하고 읽기 좋은 표현으로 나타낼 수 있죠. 물론 코틀린에서는 추가적인 가변 변수를 만들고 같은 코드를 명령형 스타일로 작성하는 것도 전혀 문제없어요.
이런 경쟁 프로그래밍 작업에서 입력을 더 간결하게 읽으려면, 다음과 같은 입력 읽기 헬퍼 함수 목록을 만들어 쓸 수 있어요.
private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
이 헬퍼들을 쓰면 입력을 읽는 코드 부분이 다음과 같이 단순해져서, 문제 서술의 입력 명세를 한 줄 한 줄 그대로 따라가게 돼요.
// read input
val n = readInt()
val s = readStr()
val fl = readInts()
경쟁 프로그래밍에서는 코드를 한 번만 작성하고 그 이후에는 유지보수하지 않기 때문에, 변수 이름을 산업 현장 프로그래밍 관행보다 짧게 짓는 게 관례예요. 그래도 그 이름들은 보통 기억을 돕는(연상 가능한) 이름이에요——배열에 a, 인덱스에 i, j 등, 표의 행과 열 번호에 r, c, 좌표에 x, y 같은 식이죠. 문제 서술에 나온 그대로 입력 데이터에 같은 이름을 쓰면 더 쉬워요. 다만 복잡한 문제일수록 더 많은 코드가 필요해서, 결국 길고 스스로 설명되는 변수·함수 이름을 쓰게 돼요.
추가 팁과 요령 (More tips and tricks)
경쟁 프로그래밍 문제는 종종 이런 형태의 입력을 가져요.
입력의 첫 줄에 두 정수 n과 k가 들어 있다.
코틀린에서는 정수 목록의 구조 분해 선언(destructuring declaration)을 쓰는 다음 문장으로 이 줄을 간결하게 파싱할 수 있어요.
val (n, k) = readInts()
구조가 덜 잡힌 입력 형식을 파싱하려고 JVM의 java.util.Scanner 클래스를 쓰고 싶어질 수도 있어요. 코틀린은 JVM 라이브러리와 잘 연동되도록 설계돼서, 그 라이브러리들을 쓰는 느낌이 코틀린에서는 꽤 자연스러워요. 다만 java.util.Scanner는 극도로 느리다는 점을 조심하세요. 실제로 너무 느려서, 10^5개 이상의 정수를 파싱하는 일은 전형적인 2초 시간 제한 안에 들어오지 못할 수 있어요. 코틀린의 단순한 split(" ").map { it.toInt() }라면 충분히 처리할 수 있는 양이에요.
코틀린에서 출력을 작성하는 건 보통 println(...) 호출과 코틀린의 문자열 템플릿을 써서 간단하게 해요. 다만 출력이 10^5줄 이상 될 때는 주의가 필요해요. 이렇게 많은 println 호출을 내보내는 건 너무 느려요. 코틀린의 출력은 줄마다 자동으로 flush되거든요. 배열이나 리스트에서 여러 줄을 빠르게 쓰는 방법은 구분자로 "\n"을 쓰는 joinToString() 함수를 사용하는 거예요.
println(a.joinToString("\n")) // each element of array/list of a separate line
코틀린 배우기
코틀린은 배우기 쉬워요. 특히 이미 자바를 아는 사람이라면 더 쉬운데요. 소프트웨어 개발자를 위한 코틀린 기본 문법 소개는 사이트의 기본 문법(basic syntax)에서 시작하는 레퍼런스 섹션에서 바로 찾을 수 있어요.
IDEA에는 내장된 Java-to-Kotlin 변환기가 있어요. 자바에 익숙한 사람이 이 변환기로 해당하는 코틀린 문법 구성을 배울 수 있어요. 다만 완벽하진 않으니, 여전히 코틀린 자체에 익숙해지고 코틀린 관용구(idiom)를 배우는 편이 좋아요.
코틀린의 문법과 코틀린 표준 라이브러리 API를 공부하는 좋은 자료로 Kotlin Koans가 있어요.