[programmers / python] 해시(Hash) - 완주하지 못한 선수

 

def solution(participant, completion):
    hs = {}
    
    for i in range(len(participant)) :
        if participant[i] not in completion :
            return participant[i]
        else :
            if participant[i] not in hs.keys() :
                hs[participant[i]] = 1 
            else :
                return participant[i]
    
    return (0)

👇 hash 이용한 풀이법

 

조건을 보면, 참가자와 완주자는 단 한명만이 차이난다.

그래서 그 한명만 찾아내면 되기에

1) 참가자의 명단을 반복문을 돌려, 참가자의 이름이 완주자 명단에 있는지 확인한다.

    참가자의 이름 중 완주자 명단에 존재하지 않는 이름이 있다면, 완주하지 못한 선수를 찾은 것이므로,

    그 참가자의 이름을 반환한다.

2) 참가자의 이름이 모두 완주자 명단에 있다면, 완주하지 못한 선수는 중복된 이름 중 하나라는 것을 알 수 있다. 

    참가자의 이름을 key 값으로 저장하여 중복된 이름을 찾아낼 건데,

    딕셔너리 내에 이미 같은 key 값이 존재한다면, 중복되었음을 의미하므로 반환하고, 존재하지 않으면 저장한다.

그러나 결과는 정확성 30/50, 효율성 0/50, 도합 30/100 점

특히나 효율성이 0점인 것은 시간초과 된 것이기 때문에 코드를 간단하게 고쳐본다.

def solution(participant, completion):
    
    for i in participant :
        if i in completion :
            participant.remove(i)
            completion.remove(i)
        else :
            return i

    return (0)

👇 hash 이용하지 않고 이름을 명단에서 삭제하는 풀이법

 

hash 해시 카테고리에 있지만, 해시를 이용하지 않아야 코드가 간단해졌다.

근데 한가지 문제가 있다.

변수 i 로 참가자의 명단을 반복할 때,

처음 i 는 participant[0] 의 값을 가지지만, 삭제가 이루어 진다면,

participant[0] 이 삭제되어 participant[1] 의 값이 participant[0] 으로 위치를 바꾸고, 

participant[2] 의 값이 participant[1] 으로 위치가 바뀌므로, 

결국 삭제되기 전 리스트에서 participant[2]의 값이 두 번째 i 가 되기에

participant 리스트의 모든 원소를 반복문을 돌릴 수가 없다.

그래서 다 틀렸다.

정확성 10/50, 효율성 0/50, 도합 10/100 점의 코드

 

def solution(participant, completion):
    
    while ( len(participant) != 0 ) :
        pp = participant[0]
        if pp in completion :
            participant.remove(pp)
            completion.remove(pp)
        else :
            return pp

    return (0)

정확성 50/50, 효율성 0/50, 도합 50/100

효율성에서 시간초과가 나왔다.

 

def solution(participant, completion):
    
    for i in range(len(participant)) :
        if participant[i] not in completion :
            return participant[i]
        else :
            completion.remove(participant[i])

효율성 시간초과.. 반복문을 덜 돌릴 수가 있나 ? 

'얼마나 더..' 라는 생각이 들었지만, 고쳐본다

 

def solution(participant, completion):
    participant = sorted(participant)
    completion = sorted(completion)
    
    for i in range(len(completion)) :
        if participant[i] != completion[i] :
            return participant[i]
        elif i == ( len(completion) -1 ) :
            return participant[i+1]

반복문을 한번만 돌릴려고 정렬을 이용했다.

그러면 인덱스로만 반복문을 한번만 돌려도 찾아낼 수 있기 때문이다.

ㅠㅠ

드디어 정확성 50/50, 효율성 50/50, 도합 100/100 점이다