[해시] 폰켓몬_프로그래머스

폰켓몬_프로그래머스

Programmers-LeetCode/Python3/프로그래머스/1/1845. 폰켓몬 at main · crystal397/Programmers-LeetCode

 

1. 해시의 정의

• 해시는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다
• 키(Key)와 값(Value)을 쌍으로 데이터를 저장하는 자료구조입니다
• 파이썬에서는 딕셔너리(Dictionary)가 해시 테이블을 구현한 자료구조입니다

2. 해시가 유용한 상황

• 데이터의 빠른 검색이 필요할 때 (O(1) 시간 복잡도)
• 중복된 요소를 확인해야 할 때
• 요소의 개수를 세야 할 때
• 특정 값의 존재 여부를 확인해야 할 때

3. 파이썬에 적용되는 해시 개념

# 딕셔너리 생성
hash_map = {}  # 빈 딕셔너리
hash_map = dict()  # 빈 딕셔너리
hash_map = {'key1': 'value1', 'key2': 'value2'}  # 초기값이 있는 딕셔너리

# 기본 연산
hash_map['new_key'] = 'new_value'  # 삽입
value = hash_map['key1']  # 조회
del hash_map['key1']  # 삭제

# 유용한 메서드들
hash_map.get('key', 'default')  # key가 없을 때 default 반환
hash_map.keys()    # 모든 키 반환
hash_map.values()  # 모든 값 반환
hash_map.items()   # (key, value) 쌍 반환

 

4. 파이썬 유용한 내장 collections 함수

# Counter 함수

from collections import Counter

# 예시 데이터
counter1 = Counter(['a', 'a', 'b', 'b', 'c', 'c', 'd'])
counter2 = Counter(['a', 'b', 'b', 'c', 'd', 'd'])

# Counter 뺄셈
result = counter1 - counter2

print("Original counters:")
print("Counter1:", counter1)  # Counter({'a': 2, 'b': 2, 'c': 2, 'd': 1})
print("Counter2:", counter2)  # Counter({'b': 2, 'd': 2, 'a': 1, 'c': 1})
print("Result:", result)      # Counter({'a': 1, 'c': 1})

# 방법 1: 원본 counter1의 키들 중에서 result에 없는 키 찾기
zero_keys = [key for key in counter1.keys() if key not in result]
print("Keys with zero value:", zero_keys)  # ['b', 'd']

# 방법 2: 뺄셈 전에 키들을 저장해두고, 결과에서 확인
original_keys = set(counter1.keys())
zero_keys = [key for key in original_keys if key not in result]
print("Keys with zero value:", zero_keys)  # ['b', 'd']

 

# defaultdict 함수

from collections import defaultdict

# defaultdict는 존재하지 않는 키로 접근할 때
# 지정한 타입(list, int, str 등)의 기본값을 자동으로 생성합니다

# 예시 1: 그래프 구현
graph = defaultdict(list)
graph[1].append(2)  # 키 1이 없지만, 자동으로 빈 리스트 []가 생성됨
graph[1].append(3)  # 키 1의 리스트에 3을 추가
print(graph)  # defaultdict(<class 'list'>, {1: [2, 3]})

# 일반 딕셔너리와 비교
normal_dict = {}
# normal_dict[1].append(2)  # KeyError 발생!
# 일반 딕셔너리는 없는 키에 접근하면 에러가 발생합니다

# 예시 2: 단어 빈도수 계산
word_count = defaultdict(int)
words = ['apple', 'banana', 'apple', 'cherry', 'banana']

for word in words:
    word_count[word] += 1  # 키가 없어도 0으로 초기화되어 +1이 가능
print(word_count)  # defaultdict(<class 'int'>, {'apple': 2, 'banana': 2, 'cherry': 1})

# 예시 3: 문자열 그룹화
strings = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
anagram_groups = defaultdict(list)

for s in strings:
    # 정렬된 문자열을 키로 사용
    sorted_str = ''.join(sorted(s))
    anagram_groups[sorted_str].append(s)

print(dict(anagram_groups))
# {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

 

1차 풀이

def solution(nums):
    if len(set(nums)) > len(nums) / 2:
        return (len(nums) / 2)
    else:
        return len(set(nums))

 

2차 풀이

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