백준 - 내 선물을 받아줘 2(Kotlin)

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

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

 

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

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

문의는 댓글 바람.

 

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

 

[문제 설명]

언뜻보면 단순한 리스트처럼 보이지만 그래프로 생각하면 몇개의 그래프를 가지는지 찾는 문제다.

parents 배열을 이용하여 해당 노드의 시작점을 기록했다.

단, 시작점이 여러 곳일 수도 있으므로 노드 번호가 작은 애를 우선순위로 뒀다.

 

 

[접근 방법]

fun main() {
    readln()
    val map = readln().toCharArray()
    val parents = IntArray(map.size) { it }
    val visited = BooleanArray(map.size)

    for (i in map.indices) {
        var currentParent = i
        var currentPoint = i
        if (visited[i]) {
            continue
        }
        visited[i] = true

        while (true) {
            val nextPoint = when (map[currentPoint]) {
                'W' -> {
                    currentPoint - 1
                }
                else -> {
                    currentPoint + 1
                }
            }

            currentParent = currentParent.coerceAtMost(parents[nextPoint])
            parents[currentPoint] = currentParent
            parents[nextPoint] = currentParent

            if (visited[nextPoint]) {
                break
            }
            visited[nextPoint] = true

            currentPoint = nextPoint
        }
    }

    println(parents.distinct().size)
}

[내 답안 수정하기]

다른 사람 답안을 보는데 단순히 EW가 만나면 한 그래프가 완성 된다.

코드도 굉장히 간단하고 시간복잡도도 O(N)으로 깔끔하다.

위의 방법처럼 그래프 시작점을 저장할 필요도 없으므로 공간 복잡도도 O(1)로 깔끔하다. 그냥 그렇게 푸세요.