[BaekJoon] 2252번 줄 세우기 (Kotlin) 문제 풀이 [Gold 3]

문제

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

2252번: 줄 세우기

 

어떻게 풀 것인가?

주어진 수 대로 두 학생의 키를 비교하면 된다. 

즉, 주어진 예제의 정답처럼 답이 나오지 않더라도, 순서만 맞다면 정답이 처리된다.

 

학생이 각각 노드라고 생각하고 주어진 조건을 간선이라고 생각한다면 위상정렬로 문제를 풀어야 한다.

 

다른 분들의 풀이를 참고하니 단순 배열이나 리스트를 이용한 정렬을 이용하면 시간초과가 발생한다고 한다.

 

풀면서 놓쳤던점

없었다. 다만 코틀린으로 위상정렬를 짜려고하다보니 처음에 많이 버벅거렸다.

 

이 문제를 통해 얻어갈 것

위상 정렬의 기본 이해

 

내 코드 

import java.lang.StringBuilder
import java.util.*

// 백준알고리즘 2252번 줄 세우기
fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    val N = st.nextToken().toInt()
    val M = st.nextToken().toInt()
    val sb = StringBuilder()

    val edgeCount = IntArray(N + 1)

    val graph = ArrayList<ArrayList<Int>>()
    for (i in 0..N) {
        graph.add(ArrayList())
    }

    for (i: Int in 1..M) {
        st = StringTokenizer(readLine())
        val first = st.nextToken().toInt()
        val second = st.nextToken().toInt()
        graph[first].add(second)
        edgeCount[second]++
    }

    val q: Queue<Int> = LinkedList()

    for (i: Int in 1..edgeCount.lastIndex) {
        if (edgeCount[i] == 0) {
            q.offer(i)
        }
    }

    while (!q.isEmpty()) {
        val nodeNo = q.poll()
        val list: List<Int> = graph[nodeNo]
        sb.append(nodeNo).append(" ")
        for (i in list.indices) {
            edgeCount[list[i]]--
            if (edgeCount[list[i]] == 0) {
                q.offer(list[i])
            }
        }
    }
    println(sb)

}

 

참고

https://codingnojam.tistory.com/66

[Algorithm] 위상정렬(Topological Sort)을 Java로 구현해보자!!