백준 1920번 코틀린

정말 간단한 문제라서 슈루룩 풀어버리고 다음 문제로 넘어가려고 했는데 이게 웬 걸? 시간 초과가 떴습니다..

처음엔 그래서 그냥 출력 문젠가 싶어서 println을 BufferedWriter로 바꾸어 보았는데도 시간 초과가 뜨더군요.

 

다시보니 문제 제한 시간이 1초뿐이고 입력은 10만 개까지도 들어와서 그게 문제였습니다.

 

그래서 고쳐서 낸 코드는 다음과 같습니다.

fun main() {
    readLine() // n
    val arr1 = readLine()!!.split(" ").sorted()
    readLine() // m
    val arr2 = readLine()!!.split(" ").map { if (arr1.binarySearch(it) >= 0) 1 else 0 }
    arr2.forEach { println(it) }
}

n이랑 m은 필요 없어서 변수 할당도 안 하고 그냥 readLine으로 읽자마자 바로 버립니다.

현대 언어들은 저런 거 입력으로 던져줄 필요 없이 그냥 배열만으로도 배열의 길이를 알 수 있는데 C언어 같은 건 n 알려주지 않고는 배열을 할당할 수가 없기 때문에 저런 입력이 항상 들어오는데 코틀린 입장에서는 귀찮기만 합니다.

 

처음엔 저런 거 val n = readLine()!!.toInt() 해주었는데 그렇게 하면 n 쓰지도 않는데 변수 할당했다고 경고를 띄웁니다...

차라리 그냥 readLine()으로 읽고 버려버리는 코드가 더 빠르고, 입력하기도 쉽고, 경고도 안 뜹니다.

 

참고로 처음에 시간 초과가 난 코드는 다음과 같습니다.

 

fun main() {
    readLine()
    val arr1 = readLine()!!.split(" ")
    readLine()
    val arr2 = readLine()!!.split(" ").map { if (arr1.contains(it)) 1 else 0 }
    arr2.forEach { println(it) }
}

5번째 줄에서 contains를 사용한 게 문제였습니다. println 같은 걸 전부 버퍼 출력으로 바꿔보기도 하고 split을 StringTokenizer 같은 걸로 바꿔보기도 했는데 전부 다 소용 없었습니다.

 

그냥 contains를 binarySearch로 바꿔주면 됩니다. binarySearch는 코틀린에 기본 내장되어있기 때문에 따로 구현할 필요가 없습니다. 찾는 원소가 없을 경우엔 음수를, 있을 경우엔 해당 인덱스 번호를 반환하는 함수입니다.

 

물론 binarySearch는 정렬된 함수에서만 제대로 동작하므로 3번째 줄에 arr1을 .sorted() 상태로 저장해주는 건 필수입니다.