백준 - 추월(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2002

 

[문제 설명]

추월한 자동차가 몇대인지 체크하시오.

[접근 방법]

추월한 자동차의 조건은 들어올 때 자기 앞에 있는 자동차들중 한대라도 자기 뒤에 있어야 한다.

Map으로 key를 기준이 되는 자동차로 두고, value를 앞에 있던 자동차로 저장한다.

앞에 있던 자동차 중에 한 대라도 뒤로 갔을 경우, 그 차는 추월한 차다.

시간복잡도는 O(N^2)

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var cntOfOvertakeCar = 0
    // 입력
    val N = readLine().toInt()
    // 들어온 순서
    val orderOfEntered = Array<String>(N) {"        "}
    // 나가는 순서
    val orderOfLeft = Array<String>(N){"        "}
    repeat(N) { orderOfEntered[it] = readLine() }
    repeat(N) { orderOfLeft[it] = readLine() }

    // key는 차 번호, value는 앞에 있던 차들을 담을 Set
    val map = HashMap<String, ArrayList<String>>()
    for (i in orderOfEntered.indices) {
        for (j in 0 until i) {
            if (i == j) continue
            if (map[orderOfEntered[i]] == null) {
                map[orderOfEntered[i]] = ArrayList()
            }
            map[orderOfEntered[i]]?.add(orderOfEntered[j])
        }
    }

    for (i in orderOfLeft.indices) {
        var isOvertake = false
        for (j in i+1 until orderOfLeft.size) {
            // 아예 앞에 차가 없었으면. -> map[orderOfLeft[i]]가 null이면 추월할 일이 없으므로 무조건 추월 안함.
            // -> isOverTake는 false가 추월한 차 개수는 더하지 않음.

            // 뒤에 있는 차가, 앞에 있던 차였으므로 추월한 차가 맞음.
            if (map[orderOfLeft[i]]?.contains(orderOfLeft[j]) == true) {
                isOvertake = true
                break
            }
        }

        // 추월한 차이므로 +1
        if (isOvertake) {
            cntOfOvertakeCar++
        }
    }

    println(cntOfOvertakeCar)
}