nums라는 숫자 리스트가 주어졌다고 가정해 보겠습니다. 리스트의 각 숫자는 특정 후보에게 던진 한 표를 나타냅니다. 이때 전체 표 수 n의 1/3, 즉 floor(n/3)(n÷3의 몫)보다 많은 표를 얻은 후보들의 id를 오름차순으로 구하는 것이 이번 문제입니다.
예를 들어 입력이 nums = [3, 2, 6, 6, 6, 6, 7, 7, 7, 7, 7]이라면 결과는 [6, 7]이 됩니다. 총 11표 중 후보 6은 4표, 후보 7은 5표를 얻어 두 후보 모두 n/3(약 3.67표)을 초과하는 득표율을 기록했기 때문입니다.
해결 접근 방법
이 문제는 리스트를 정렬한 뒤 일정한 간격으로 값을 검사하는 방식으로 효율적으로 풀 수 있습니다. 단계별 과정은 다음과 같습니다.
ans: 결과를 저장할 빈 집합(set)을 생성합니다.- 리스트
nums를 오름차순으로 정렬합니다. i = 0,n = len(nums)으로 초기화합니다.i가 리스트 길이보다 작은 동안 반복합니다.nums[i]의 등장 횟수가n // 3보다 크면ans에 추가합니다.i를n // 3만큼 증가시킵니다.
ans를 정렬된 리스트 형태로 반환합니다.
왜 이 방법이 동작할까?
리스트를 정렬하면 같은 후보의 표는 항상 연속된 구간에 모이게 됩니다. 어떤 후보가 n/3보다 많은 표를 얻었다면 그 구간의 길이 역시 n/3보다 길어야 하므로, 0부터 시작해 n/3 간격으로 위치를 검사하면 해당 구간 안에서 최소 한 번은 반드시 그 후보를 만나게 됩니다. 검사 지점이 최대 3~4곳에 불과하기 때문에 모든 요소를 하나씩 확인하는 것보다 훨씬 적은 비교 횟수로 답을 구할 수 있습니다.
구현 예제
class Solution: def solve(self, nums): ans = set([]) nums.sort() i = 0 n = len(nums) while i < len(nums): if nums.count(nums[i]) > n // 3: ans.add(nums[i]) i += n // 3 return sorted(list(ans)) ob = Solution() nums = [3, 2, 6, 6, 6, 6, 7, 7, 7, 7, 7] print(ob.solve(nums))
입력
[3, 2, 6, 6, 6, 6, 7, 7, 7, 7, 7]
출력
[6, 7]
복잡도 분석
정렬에 O(n log n)의 시간이 소요되며, 검사 지점은 약 3~4곳뿐이므로 각 지점에서 count()를 호출하는 비용까지 포함해도 전체 시간 복잡도는 O(n log n) 수준입니다. 공간 복잡도는 결과를 저장하는 집합을 제외하면 O(1)로 매우 효율적입니다.