문제 개요
투표 데이터가 리스트 형태로 주어진다고 가정해 봅시다. 리스트의 각 요소는 두 개의 값을 가지는 배열 [c_id, v_id]이며, 여기서 c_id는 후보자(candidate)의 ID, v_id는 투표자(voter)의 ID를 의미합니다.
우리의 목표는 특정 투표자가 두 번 이상 투표했는지, 즉 부정 행위가 발생했는지를 확인하는 것입니다.
예를 들어 입력이 다음과 같다면,
[[5, 1], [5, 0], [5, 4], [5, 3], [5, 0]]
출력은 True가 됩니다. 그 이유는 [5, 0], 즉 ID가 0인 투표자가 동일한 후보에게 두 번 투표했기 때문입니다.
해결 접근 방식
이 문제는 집합(Set) 자료구조를 활용하면 간단하게 해결할 수 있습니다. 집합은 중복된 값을 저장하지 않으므로, 전체 투표 수와 고유한 투표자 수를 비교하는 방식으로 중복 여부를 판별할 수 있습니다.
해결 단계는 다음과 같습니다.
- 새로운 집합(set)을 생성합니다.
- 투표 목록을 순회하면서 각 투표의 투표자 ID(
vote[1])를 집합에 추가합니다. - 집합의 크기와 원본 투표 목록의 크기를 비교합니다.
- 두 크기가 다르면 중복 투표가 존재한다는 의미이므로
True를 반환하고, 같으면False를 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, votes):
all = set()
for vote in votes:
all.add(vote[1])
return len(all) != len(votes)
ob = Solution()
votes = [[5, 1], [5, 0], [5, 4], [5, 3], [5, 0]]
print(ob.solve(votes))
입력
[[5, 1], [5, 0], [5, 4], [5, 3], [5, 0]]
출력
True
코드 설명 및 복잡도 분석
위 코드에서 solve 메서드는 빈 집합을 생성한 뒤, 모든 투표를 한 번씩 순회하며 투표자 ID만 집합에 추가합니다. 집합은 중복을 허용하지 않기 때문에, 동일한 투표자가 여러 번 투표했다면 집합에는 한 번만 저장됩니다.
따라서 최종적으로 집합의 크기(len(all))가 전체 투표 수(len(votes))보다 작다면, 누군가 중복 투표를 했다는 뜻이 됩니다.
- 시간 복잡도: O(n) — 투표 목록을 한 번만 순회하면 되므로 매우 효율적입니다.
- 공간 복잡도: O(n) — 최악의 경우 모든 투표자 ID를 집합에 저장해야 합니다.
이처럼 Python의 집합 자료구조를 활용하면 중복 검사 문제를 직관적이고 효율적으로 해결할 수 있습니다.