글 읽기 - [Kotlin][시간초과]python으론 통과, kotlin으론 시간초과

gi4642 2년 전 0

어느 부분을 고쳐야 시간 초과를 해결할 수 있을까요?

import java.util.*

fun main(args: Array<String>) = with(Scanner(System.`in`)) {

    fun dfs(x:Int,
            adj:Map<Int, List<Int>>,
            chk:Array<Boolean>,
            label:MutableMap<Int, Int>,
            prev:Int,
            res:MutableList<Int>
            ) {
        chk[x] = true
        if (!label.containsKey(x)) {
            label[x] = (prev * -1)
        }
        
        for (y in adj[x]!!) {
            if (y in label.keys && label[y] == label[x]) {
                res.add(1)
                break
            }
            if (chk[y] == false) {
                dfs(y, adj, chk, label, label[x]!!, res)
            }
        }
    }


    fun check(adj:Map<Int, List<Int>>, chk:Array<Boolean>) {
        val res = mutableListOf<Int>()
        var start = 1
        for (x in adj.keys) {
            if (start == 1) {
                dfs(x, adj, chk, mutableMapOf<Int, Int>(), 1, res)
                start = 0
            }
            if (chk[x] == false) {
                dfs(x, adj, chk, mutableMapOf<Int, Int>(), 1, res)
            }
        }
        if (res.isEmpty()) {
            println("YES")
        } else {
            println("NO")
        }
    }
    
    val test_case = nextInt()
    
    for (x in (1..test_case)) {
        val V = nextInt()
        val E = nextInt()
        val checker = Array(V+1) { false }
        val edges = (1..E).map { listOf(nextInt(), nextInt()) }
        val tmpMap1 = edges.groupBy { it.component1() }
            .mapValues { out_ -> out_.value.flatten().filter { in_ -> in_ > out_.key } }
        val tmpMap2 = edges.groupBy { it.component2() }
            .mapValues { out_ -> out_.value.flatten().filter { in_ -> in_ > out_.key } }
        val adj = (tmpMap1.asSequence() + tmpMap2.asSequence()).distinct()
            .groupBy({ it.key }, { it.value })
            .mapValues { it.value.flatten() }
        
        check(adj, checker)
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Kotlin][시간초과]python으론 통과, kotlin으론 시간초과

gi4642 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말