[Scala] BOJ 1920 - 수 찾기

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

import scala.io.StdIn

object Constants{
	final val VERBOSE = false
}

object Main{
	def main(args:Array[String]):Unit={
		val N:Int = StdIn.readInt()
		if(Constants.VERBOSE) println(N)
		val Target:Vector[Int] = StdIn.readLine().split(" ").map(x => x.toInt).toVector
		if(Constants.VERBOSE) println(Target)
		val M:Int = StdIn.readInt()
		if(Constants.VERBOSE) println(M)
		val Search:Vector[Int] = StdIn.readLine().split(" ").map(x => x.toInt).toVector
		if(Constants.VERBOSE) println(Search)

		Search.foreach(x => println(if(Target.contains(x)) 1 else 0))
	}
}

결과: 시간초과

• 스칼라가 좀 느리긴 하던데(C에서 200ms걸리는게 2000ms나 걸림), 아예 Timeout Error가 뜰 줄이야...
• 아마, Vector에 넣고 10만개짜리 원소 배열에서 해당 원소의 유무를 10만회 비교하는 과정에서, 타임아웃 난 듯 하다.
• 그렇다면, Set이라던지, 존재여부판별에 최적화된 Tree같은 자료구조를 쓰는 수밖에...C++였으면 set이 있겠는데.
• 알고보니 set으로 푼 사람이 있다. 딱 1명. Scala 국내에 진짜 자료 없구나...

Set 도입했다.
Scala 실행시간은 2988ms.
Python이 232ms, C가 72ms인데 너무나도너무나도너무나도 느린 속도다.
이게 맞냐...? 왜이렇게 느려.

import scala.io.StdIn
import scala.collection.mutable.Set

object Constants{
	final val VERBOSE = false
}

object Main{
	def main(args:Array[String]):Unit={
		val N:Int = StdIn.readInt()
		if(Constants.VERBOSE) println(N)
		val Target:Vector[Int] = StdIn.readLine().split(" ").map(x => x.toInt).toVector
		var setTarget:Set[Int] = Set[Int]()
		for (t <- Target) setTarget += t
		if(Constants.VERBOSE) println(Target)

		val M:Int = StdIn.readInt()
		if(Constants.VERBOSE) println(M)
		val Search:Vector[Int] = StdIn.readLine().split(" ").map(x => x.toInt).toVector
		if(Constants.VERBOSE) println(Search)

		 for(s <- Search) {
			if(setTarget contains s) println(1) else println(0)
		 }
	}
}

좀더 최적화해봄. 사실, Array[Int]를 Vector로 바꾸는 과정은 불필요함.

import scala.io.StdIn
import scala.collection.mutable.Set

object Constants{
	final val VERBOSE = false
}

object Main{
	def main(args:Array[String]):Unit={
		val N:Int = StdIn.readInt()
		if(Constants.VERBOSE) println(N)
		val Target = StdIn.readLine().split(" ").map(x => x.toInt)
		var setTarget:Set[Int] = Set[Int]()
		for (t <- Target) setTarget += t
		if(Constants.VERBOSE) println(Target.getClass)

		val M:Int = StdIn.readInt()
		if(Constants.VERBOSE) println(M)
		val Search = StdIn.readLine().split(" ").map(x => x.toInt)
		if(Constants.VERBOSE) println(Search.getClass)

		 for(s <- Search) {
			if(setTarget contains s) println(1) else println(0)
		}
	}
}

• Target 변수의 자료형은 Target.getClass 결과, class [I 로 나왔는데
  이것은 Java의 Byte코드에서 Integer Array를 나타내는 관례라고 한다.
• 2467ms 나왔다. 내가 이 문제 백준의 Scala 속도 기록을 깼다(....ㅋㅋㅋ)

Scala Collection 자료형 참고
https://groups.google.com/g/scala-korea/c/j7ucQeI7Lyg?pli=1