[백준] #2002: 추월

1. Problem Link

• https://www.acmicpc.net/problem/2002

2. Notation

• n: number of cars passing through tunnel.
• dae: car number list written by 대식.
• carToIndexMap: a map data structure with car number written by 대식 as a key and index as a value.
• indexToIndexMap: a map data structure with index from dae list as a key and index from 영식's car number list as a value.

3. Source Code

• We convert 대식's car number to index.
• We get 영식's car number one by one.
• With 영식's car number, we get an index from carToIndexMap. Then, store the index as a key and current index as a value.

<대식>
ZG431SN -> 0
ZG5080K -> 1
ST123D -> 2
ZG206A -> 3

<영식>
ZG206A -> 3 -> 0
ZG431SN -> 0 -> 1
ZG5080K -> 1 -> 2
ST123D -> 2 -> 3

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val dae = mutableListOf<String>()
    val carToIndexMap = mutableMapOf<String, Int>()
    val indexToIndexMap = mutableMapOf<Int, Int>()

    repeat(n) { index ->
        val car = br.readLine()
        dae.add(car)
        carToIndexMap[car] = index
    }
    repeat(n) { index ->
        val car = br.readLine()
        indexToIndexMap[carToIndexMap[car]!!] = index
    }

    val stack = mutableListOf<Int>()
    // ZG431SN -> 0 -> 1
    stack.add(indexToIndexMap[carToIndexMap[dae[0]]!!]!!)
    var answer = 0

    for (i in 1 until n) {
        val index = indexToIndexMap[carToIndexMap[dae[i]]!!]!!
        if (stack.last() < index) stack.add(index)
        // passing by car
        else answer++
    }
    bw.write("$answer")

    br.close()
    bw.close()
}

4. Complexity

• Time: O(N), N is number of cars passing through tunnel.
• Space: O(N)