숫자로 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 이 리스트에는 총 n개의 값이 담겨 있으며, 각 숫자는 특정 후보에게 표를 던진 투표를 의미합니다. 우리가 구해야 할 것은 전체 표 수의 절반을 넘는, 즉 floor(n/2)보다 많은 득표를 기록한 후보의 ID입니다. 만약 과반수 득표를 한 후보가 존재하지 않는다면 -1을 반환하면 됩니다.
예를 들어 입력이 nums = [6, 6, 2, 2, 3, 3, 3, 3, 3]이라면 어떻게 될까요? 전체 표는 9개이고, 숫자 3은 5번 등장하므로 floor(9/2) = 4보다 많습니다. 따라서 과반수를 확보한 후보는 3이며, 출력 결과도 3이 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 변수 l에 리스트 nums의 크기를 저장합니다.
- 각 숫자별 등장 횟수를 세어 맵(count) 형태로 저장합니다.
- 맵에 있는 각 숫자 i와 그 등장 횟수 j를 하나씩 확인하면서, j가 l / 2보다 크면 해당 숫자 i를 반환합니다.
- 모든 숫자를 확인했는데도 조건을 만족하는 값이 없다면 -1을 반환합니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, nums):
l = len(nums)
from collections import Counter
count = Counter(nums)
for i, j in count.items():
if j > (l // 2):
return i
return -1
ob = Solution()
nums = [6, 6, 2, 2, 3, 3, 3, 3, 3]
print(ob.solve(nums))
입력
[6, 6, 2, 2, 3, 3, 3, 3, 3]
출력
3
코드 상세 설명
핵심 역할을 하는 것은 Python 표준 라이브러리의 collections.Counter입니다. Counter는 리스트를 인자로 받아 각 요소의 등장 횟수를 딕셔너리 형태로 자동 계산해 주므로, 별도의 반복문으로 개수를 세는 번거로움을 줄여 줍니다.
- l = len(nums): 전체 표의 개수를 구합니다.
- count = Counter(nums): {6: 2, 2: 2, 3: 5}처럼 숫자별 득표 수가 정리된 맵이 생성됩니다.
- if j > (l // 2): 정수 나눗셈(//)을 사용해 과반수 기준인 floor(n/2)를 계산하고, 이를 초과하는 후보를 찾습니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) – 리스트를 한 번 순회하며 카운트를 만들고, 고유 값의 개수만큼만 추가로 확인합니다.
- 공간 복잡도: O(n) – 고유 숫자의 개수만큼 맵에 저장 공간이 필요합니다.
참고로, 메모리 사용을 줄이고 싶다면 Boyer–Moore 과반수 투표 알고리즘을 사용해 O(n) 시간과 O(1) 공간으로도 같은 문제를 해결할 수 있습니다. 다만 과반수 후보가 반드시 존재한다는 보장이 없는 이 문제에서는, 위처럼 Counter로 검증하는 방식이 더 직관적이고 안전한 선택입니다.