숫자로 이루어진 리스트 nums가 주어졌을 때, 리스트 안에서 자신의 값과 출현 빈도가 정확히 일치하는 요소가 존재하는지 확인하는 문제입니다.
예를 들어 입력이 [2, 4, 8, 10, 4, 4, 4]라면 출력은 True가 됩니다. 그 이유는 숫자 4가 리스트에 정확히 4번 등장하기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 각 값의 빈도를 저장할 새로운 딕셔너리(맵) res를 생성합니다.
- 리스트를 순회하면서 각 숫자의 출현 횟수를 계산해 저장합니다.
- 딕셔너리의 각 키-값 쌍 (k, v)를 하나씩 확인합니다.
- k가 v와 같다면, 즉 값과 그 값의 빈도가 일치하면 True를 반환합니다.
- 모든 쌍을 확인한 후에도 일치하는 항목이 없으면 False를 반환합니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, nums):
res = {}
for i in nums:
try:
res[i] += 1
except:
res[i] = 1
for k,v in res.items():
if k == v:
return True
return False
ob = Solution()
print(ob.solve([2, 4, 8, 10, 4, 4, 4]))
입력
[2, 4, 8, 10, 4, 4, 4]
출력
True
더 간결한 방법: collections.Counter 활용
파이썬에서는 collections 모듈의 Counter 클래스를 사용하면 빈도 계산 로직을 훨씬 간결하게 작성할 수 있습니다. try-except 블록 없이 한 줄로 빈도 딕셔너리를 만들 수 있습니다.
from collections import Counter
class Solution:
def solve(self, nums):
freq = Counter(nums)
return any(k == v for k, v in freq.items())
ob = Solution()
print(ob.solve([2, 4, 8, 10, 4, 4, 4])) # True
Counter는 반복 가능한 객체를 받아 각 요소의 개수를 자동으로 세어주므로, 직접 딕셔너리를 관리하는 것보다 가독성과 유지보수 측면에서 유리합니다. any() 함수는 조건을 만족하는 항목이 하나라도 있으면 즉시 True를 반환하므로 효율적입니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 리스트의 길이입니다. 리스트를 두 번 순회하지만 각 순회가 선형 시간에 수행되므로 전체적으로 선형 시간 복잡도를 유지합니다.