코틀린 코딩테스트 강좌, 친구 관계 파악하기

문제 설명

주어진 N명의 학생이 서로 친구 관계를 맺고 있습니다. 친구 관계는 쌍으로 주어지며,
두 명의 학생 A와 B가 친구이면, A는 B의 친구이고 B는 A의 친구입니다.
이제, 여러분은 특정 학생의 친구의 친구를 모두 파악하고,
그 수를 반환하는 함수를 구현해야 합니다.

예를 들어, 친구 관계가 다음과 같이 주어진다면:

(1, 2)
(1, 3)
(2, 4)
(3, 5)

학생 1의 친구는 2와 3이며, 이 친구들의 친구는 4와 5가 됩니다.
따라서 학생 1의 친구의 친구는 총 4명입니다.

입력 형식

friends: List>, target: Int

– friends: 친구 관계를 나타내는 튜플의 리스트,
– target: 친구의 친구를 찾고 싶은 학생

출력 형식

– 친구의 친구 수를 나타내는 정수

문제 해결 과정

친구 관계를 파악하기 위해 우리는 그래프 이론을 적용할 수 있습니다.
각 학생은 노드가 되며, 친구 관계는 경계로 나타낼 수 있습니다.
이를 통해 주어진 학생과 그 친구들의 친구를 탐색하는 방식으로 문제를 해결할 수 있습니다.

1. 그래프 구성

먼저 친구 관계를 그래프 형태로 변환해야 합니다.
각 학생을 키로 하고, 그 친구들을 값으로 하는 맵을 만들어 보겠습니다.


fun buildGraph(friends: List>): Map> {
    val graph = mutableMapOf>()
    for ((a, b) in friends) {
        graph.computeIfAbsent(a) { mutableListOf() }.add(b)
        graph.computeIfAbsent(b) { mutableListOf() }.add(a)
    }
    return graph
}

2. 친구의 친구 찾기

그래프가 구성된 이후, 특정 학생의 친구를 찾고,
그 친구의 친구 목록을 구해야 합니다.
이 때, 친구 목록이 중복되지 않도록 주의해야 합니다.


fun findFriendsOfFriends(friends: List>, target: Int): Int {
    val graph = buildGraph(friends)
    val directFriends = graph[target] ?: return 0
    val friendsOfFriends = mutableSetOf()
    
    for (friend in directFriends) {
        val friendsOfCurrentFriend = graph[friend]
        if (friendsOfCurrentFriend != null) {
            for (fof in friendsOfCurrentFriend) {
                if (fof != target && !directFriends.contains(fof)) {
                    friendsOfFriends.add(fof)
                }
            }
        }
    }
    return friendsOfFriends.size
}

3. 전체 코드

이제 전체 코드를 정리해보겠습니다.


fun main() {
    val friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5))
    val targetStudent = 1
    val result = findFriendsOfFriends(friendsList, targetStudent)
    println("학생 $targetStudent의 친구의 친구 수: $result")
}

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N + M)입니다.
여기서 N은 학생 수, M은 친구 관계의 수를 의미합니다.
공간 복잡도 또한 O(N + M)입니다.
이는 각각의 학생과 친구 관계를 그래프 형태로 저장하기 때문입니다.

예제 및 테스트 케이스

다양한 예제를 통해 함수가 올바르게 작동하는지 확인해보겠습니다.

예제 1:

입력:


                    friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5))
                    targetStudent = 1

출력: “학생 1의 친구의 친구 수: 2”

예제 2:

입력:


                    friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 3))
                    targetStudent = 1

출력: “학생 1의 친구의 친구 수: 0”

예제 3:

입력:


                    friendsList = listOf(Pair(1, 2), Pair(3, 4), Pair(4, 5))
                    targetStudent = 1