파이썬으로 팔로우 관계 목록에서 상호 팔로우(맞팔) 사용자 찾기

소셜 미디어 플랫폼에서 사람들 간의 팔로우 관계를 담고 있는 relations라는 리스트가 있다고 가정해 보겠습니다. 각 요소 relations[i]는 두 개의 숫자 [ai, bi]로 구성되며, 이는 사용자 ai가 사용자 bi를 팔로우하고 있음을 의미합니다. 우리의 목표는 서로를 맞팔로우(상호 팔로우)하는 사용자들을 모두 찾아, 정렬된 형태의 리스트로 반환하는 것입니다.

예를 들어, 입력이 relations = [[0, 2], [2, 3], [2, 0], [1, 0]]이라면, 0번 사용자와 2번 사용자가 서로를 팔로우하고 있으므로 출력은 [0, 2]가 됩니다.

문제 해결 접근 방식

이 문제는 집합(set) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 집합은 중복을 허용하지 않으면서 삽입과 조회를 평균 O(1) 시간에 처리하기 때문입니다. 알고리즘의 동작 과정은 다음과 같습니다.

• 결과를 저장할 집합 ans와 이미 확인한 관계를 저장할 집합 seen을 생성합니다.
• relations의 각 팔로우 관계 (a, b)에 대해 다음을 수행합니다.
  • 관계 (a, b)를 seen 집합에 추가합니다.
  • 만약 반대 방향인 (b, a)가 이미 seen에 존재한다면, 두 사용자 a와 b를 ans 집합에 추가합니다.
• ans의 모든 요소를 오름차순으로 정렬하여 반환합니다.

구현 예제

다음 파이썬 코드를 통해 실제 구현을 확인해 보겠습니다.

def solve(relations):
    ans = set()
    seen = set()

    for a, b in relations:
        seen.add((a, b))

        if (b, a) in seen:
            ans.add(b)
            ans.add(a)

    return sorted(ans)

relations = [
   [0, 2],
   [2, 3],
   [2, 0],
   [1, 0]
]
print(solve(relations))

입력

[[0, 2], [2, 3], [2, 0], [1, 0]]

출력

[0, 2]

시간 복잡도 분석

이 알고리즘은 각 팔로우 관계를 한 번씩 순회하며, 집합의 삽입 및 조회 연산을 O(1) 시간에 수행합니다. 따라서 전체 시간 복잡도는 관계의 개수를 n이라 할 때 O(n)입니다. 마지막 정렬 단계는 결과 집합의 크기를 m이라 할 때 O(m log m)이 추가로 소요되며, 전체적으로 매우 효율적인 해법입니다.