코딩테스트 합격자 되기 | 10. 집합 학습 정리

 

Python 코딩 테스트 학습 기록

집합은 중복을 제거하고, 값의 존재 여부를 빠르게 확인하는 자료구조다. 프로그래머스 문제를 통해 set, 정렬, 유니온-파인드를 정리한다.

폰켓몬

프로그래머스 공식 문제 페이지

가져갈 수 있는 수는 전체의 절반이고, 최대 종류 수는 중복을 제거한 종류 수를 넘을 수 없다. 따라서 두 값 중 작은 값이 답이다.

def solution(nums):
    selectable = len(nums) // 2
    kinds = len(set(nums))
    return min(selectable, kinds)

set(nums)은 같은 번호를 하나로 합친다. 종류가 100개여도 가져갈 수 있는 칸이 3개면 3종류를 넘을 수 없고, 반대로 칸이 3개인데 종류가 2개면 2종류만 가능하다.

set 기본 확인

numbers = {1, 2, 2, 3}
print(numbers)        # {1, 2, 3}

if 2 in numbers:
    print("2가 있습니다")

집합은 순서를 보장하는 목록이 아니라 중복 없는 값의 모음이다. 값이 있는지 확인하는 용도에 특히 잘 맞는다.

영어 끝말잇기

프로그래머스 공식 문제 페이지

이미 사용한 단어인지와 이전 단어의 끝 글자로 시작하는지를 함께 검사한다.

def solution(n, words):
    used = set()
    previous_last = words[0][0]

    for index, word in enumerate(words):
        if word in used or word[0] != previous_last:
            person = index % n + 1
            turn = index // n + 1
            return [person, turn]

        used.add(word)
        previous_last = word[-1]

    return [0, 0]

index % n + 1은 사람 번호, index // n + 1은 몇 번째 차례인지를 계산한다. word[-1]은 문자열의 마지막 글자다.

전화번호 목록

프로그래머스 공식 문제 페이지

문자열을 사전순으로 정렬하면 접두어 관계인 번호들이 서로 붙는다. 따라서 이웃한 두 번호만 비교하면 된다.

def solution(phone_book):
    phone_book.sort()

    for index in range(len(phone_book) - 1):
        if phone_book[index + 1].startswith(phone_book[index]):
            return False

    return True

예를 들어 ["12", "999", "12345", "1234"]를 정렬하면 ["12", "1234", "12345", "999"]가 된다. startswith()는 앞의 문자열로 시작하는지 확인한다.

집합을 이용한 대안

def solution(phone_book):
    numbers = set(phone_book)

    for number in phone_book:
        for end in range(1, len(number)):
            if number[:end] in numbers:
                return False

    return True

각 번호의 접두어를 잘라 집합에서 찾는 방법이다. 다만 번호가 길면 접두어를 여러 번 만들어야 하므로, 이 문제에서는 정렬 후 이웃 비교가 더 간단하다.

섬 연결하기

프로그래머스 공식 문제 페이지

비용이 싼 다리부터 살펴보되, 이미 같은 그룹인 두 섬을 잇는 다리는 건너뛴다. 이 방식이 크루스칼 알고리즘이며, 그룹 확인에는 유니온-파인드를 쓴다.

def find(parent, node):
    if parent[node] != node:
        parent[node] = find(parent, parent[node])
    return parent[node]

def union(parent, rank, left, right):
    left_root = find(parent, left)
    right_root = find(parent, right)

    if left_root == right_root:
        return False

    if rank[left_root] < rank[right_root]:
        parent[left_root] = right_root
    elif rank[left_root] > rank[right_root]:
        parent[right_root] = left_root
    else:
        parent[right_root] = left_root
        rank[left_root] += 1

    return True

def solution(n, costs):
    costs.sort(key=lambda cost: cost[2])
    parent = list(range(n))
    rank = [0] * n
    total_cost = 0
    edges = 0

    for left, right, cost in costs:
        if union(parent, rank, left, right):
            total_cost += cost
            edges += 1

            if edges == n - 1:
                break

    return total_cost

find()의 경로 압축은 중간 노드가 바로 루트를 가리키게 만든다. rank는 낮은 트리를 높은 트리 아래에 붙여 트리가 깊어지는 것을 줄인다. 섬이 n개면 다리 n-1개를 선택한 순간 모든 섬이 연결된다.

집합 문제 체크리스트

• 중복 제거 또는 빠른 존재 확인이면 set을 검토한다.
• 문자열 접두어는 정렬 후 이웃 비교가 가능한지 확인한다.
• 서로 연결된 그룹을 합치고 확인해야 하면 유니온-파인드를 사용한다.
• 최소 비용으로 모든 정점을 연결하면 크루스칼과 유니온-파인드를 함께 떠올린다.

마무리

집합은 단순히 중복을 없애는 도구를 넘어, 문제의 상태를 빠르게 확인하는 자료구조다. 어떤 값이 이미 등장했는지, 두 정점이 같은 그룹인지부터 구분해 보자.