[프로그래머스] Lv.1 완주하지 못한 선수(해시) Python

📍 문제 설명

📍 풀이 point

처음에 나는 participant와 동일한 리스트를 하나 만들고(copy) completion의 요소와 하나하나 비교하여, participant요소와 completion의 요소가 같으면 count를 증가시키고 count값이 1이 되는 요소를 삭제(remove)하는 방법을 사용했다.

▶ 결국 완주자를 participant에서 제거하는 방법을 이용한 것이다.

def solution(participant, completion): 
 
   participant2 = participant.copy()   # participant2 = participant 이렇게하면 B 수정시 A에도 반영되어 버림
   for i in range(len(completion)):
       count = 0
       for j in range(len(participant)):
           if participant[j] == completion[i]:
               count+=1
               if count == 1:
                   participant2.remove(participant[j])  

   return participant2[0] 

그러나, 이 경우(값 지우기(remove의 사용))에는 테스트 케이스들은 맞출 수 있었지만 시간복잡도가 높아서 효율성 테스트를 통과하지 못했다.

파이썬의 dictionary는 내부적으로 해시 테이블(Hash Table)로 구현되어 있기 때문에, 숫자 뿐만 아니라 문자, 집합까지 모두 Key로 사용이 가능할 뿐만 아니라 시간 복잡도가 list보다 낮은 O(1)이 된다.

따라서 list가 아닌 dictionary를 사용하는 것으로 코드를 수정했다.

🔓 알고리즘 순서 🔓

1) participant를 딕셔너리 형태로 바꿔준다.

2) participant에 들어있는 문자열이 해당 딕셔너리에 있으면 그 key의 value값을 +1 한다(중복체크를 위해).

3) completion에 있는 완주자 문자열이 해당 딕셔너리에 있으면 그 key의 value값을 -1 한다(완주자 제외를 위해).

def solution(participant, completion): 
      for i in dict_par.keys():
          value = dict_par.get(i)
          for j in range(len(participant)):
              if participant[j] == i :
                  value +=1
                  dict_par[i] = value

          for z in completion:
              if i==z:
                  value -=1
                  dict_par[i] = value

          if dict_par[i]!=0:
              return i

      for z in dict_par.keys():
          if dict_par.get(z) !=0:
              return z

위의 코드는 dictionary 형태로 작성한 첫 코드인데 이 또한 정답은 맞췄으나 효율성 테스트에서 실패했다...(for문의 중첩 때문으로 예상하지만 정확한 이유를 잘 모르겠음)

고민하다가 결국 다른 분들의 코드를 참고하여 통과하였다..

def solution(participant, completion): 
	dict_par = {string : 0 for string in participant}
    for i in participant:   # participant에 있으면 key값 + 1(중복체크 위해)
    	dict_par[i] +=1

 	for j in completion:   # completion에 있으면 key값 -1 
    	dict_par[j] -=1

	for z in dict_par:
    	if dict_par.get(z) == 1:
        	return z