알고리즘 - Hash

체계적인 알고리즘 학습을 위해, 파트마다 공부한 점을 블로그에 작성할 것이다.

Hash

• what ?

탐색할떄 좋은 알고리즘 ,

• when ?

예로, 전화부에서 사람을 찾을떄와 같은 탐색

• dictionary 형태

  • O(1)
  • 시간 복잡도 측면에서 LIST 보다 이득

solve - programmers

1. 완주하지 못한 선수
   

• 나의 풀이

# 정확성 100 , 효율성 0.0

def solution(participant, completion):
    

    result = []
    startlen = len(completion)
    
    
    for i in range(startlen):
        if completion[i] in participant:
            d = participant.index(completion[i])
            participant.pop(d)
    
    print("마지막 남은 사람" , participant)
        
    result = participant[0]
    
            
            
            
            
    answer = ''
    return result

위 풀이를 하였을때는, 정확성은 100% , 효율성은 시간초과로 인해 통과하지 못했다.

위 방법은, pop()을 사용해서 , 겹치는 항목을 제외시켜준 후
마지막에 남은 리스트에서 인덱스 0번으로 접근하여 추출했다.

시간초과를 해결하고자,

두 리스트를 모두 sort()를 하여 정렬시켜준 후 , for문을 돌려주었으나 , 통과하지 못했다.

• hash를 사용한 풀이

def solution(participant, completion):
    
    hashDict ={}
    sumHash = 0
    

    for part in participant:
        hashDict[hash(part)] = part
        sumHash += hash(part)
    
    for comp in completion:
        sumHash -= hash(comp)
        
    
    print(sumHash)
            
    answer = ''
    return hashDict[sumHash]

hash를 사용한 방식은,

hash 방식이 key ,value를 사용하여 값을 인식하는 방식이기에,
이를 사용한 것이다.

즉, 같은 것을 제외시키는 방식이므로,
같은 값은 같은 키값을 지니므로,
1. 하나의 sum 변수를 생서하여 여기에 key값을 더해준다.
2. 중복된 value의 key값은 sum에서 뺴준다.
3. 그렇게 하게 된다면, 마지막의 sum 값이 최종적인 한명의 key값이 되는 것이다.

이런식으로 hash를 사용하게 된다면, 위 문제를 풀 수 있다.

hash는 dictionary 기반의 알고리즘으로 , 시간복잡도에서 우수하다.

2. 폰케몬
   

위 문제는 hash개념을 익힌 후에 , 쉽게 접근하고 풀 수 있었다.

• 풀이

def solution(nums):
    
    lens = len(nums) // 2
    
    hashdict ={}
    for num in nums:
        hashdict[hash(num)] = num
        
    
    result = 0
    if lens < len(hashdict):
        result = lens
    else:
        result = len(hashdict)
    

    
    answer = 0
    return result

방법.

1. 같은 캐릭터는 같은 key값을 가지기에,
   겸치는 것을 파악하고자 , hashdict 를 생성

2. 고르고자 하는 것보다 hashdict 길이가 길 경우에는 -> nums값으로 결과내고,
   고르고자 하는 것이 hashdict 길이보다 긴 경우에는 -> hashdict길이 값으로 결과를 추출한다.