[알고리즘/해시] 완주하지 못한 선수 (프로그래머스 해시 level 1)

완주하지 못한 선수 (level 1)

코딩테스트 연습 - 완주하지 못한 선수

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

 

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

---

💡나의 문제 풀이

문제 해결 아이디어

• 해시 문제이므로, Dictionary 사전 자료형을 이용해 key:value 로 완주한 마라톤 선수의 이름으로 단번에 value 값을 찾을 수 있도록 구현해야 겠다는 아이디어를 먼저 얻었다.
  • 처음에는 True, False의 값을 value로 지정하고자 했지만, 동명이인 조건을 만족하기 위해서는 단순히 bool값으로는 해결이 불가능함을 인지했다.
• participant 리스트를 순회하며, 마라톤 선수의 이름을 key값으로, 해당 이름으로 참가한 인원 수를 value로 갖도록(0부터 초기하여 1씩 추가) playerDict 사전에 추가한다.
• completion 리스트를 순회하며, 해당 참가자에 대해 playerDict 의 value를 1씩 감소시킨다.
• 이후 , playerDict를 다시 순회하며 value 값이 1인 참가자의 이름을 리턴한다.

 

고려사항

• 참가자 중 동명이인 존재 가능 조건
  • 동명이인 중 한 명만 완주할 수도 있는 경우를 고려해야 함

 

작성 코드

def solution(participant, completion):
    playerDict = {}
    for p in participant:
        if p in playerDict:
            playerDict[p] += 1
        else:
            playerDict[p]=1
    for c in completion:
        playerDict[c]-=1

    for p, v in playerDict.items():
        if v==1:
            return p

def test():
    participant = ["mislav", "stanko", "mislav", "ana"]
    completion = ["stanko", "ana", "mislav"]    
    print(solution(participant, completion))

test()

• 첫번째 반복문을 순회할 때 2n , 두번째 반복문 순회할 때 n 이 걸리므로 총 시간 복잡도는 3n 이다.

 

---

답안 코드 1

• Collections 모듈의 Counter 함수를 이용
  • participant 리스트의 각 참가자 이름마다 몇 명이 있는지 그 인원을 카운트했고, completion 리스트의 카운트 값들을 뺌
    • counter value의 값이 1인 지원자의 이름 (key)를 리턴해야 함
    • 남아있는 Counter 객체는 남아있는 지원자 이름이기 때문에 그대로 0번째 값을 리턴하면 됨

    import collections
    def solution(participant, completion):
      answer = collections.Counter(participant) - collections.Counter(completion)
      return list(answer.keys())[0]

 

답안 코드 2

• 실제 hash() 함수를 이용해 구현한 방법 (완주하지 못한 선수가 1명이라는 조건을 만족)
  • participant를 순회하며 사전 dic에 마라톤 선수의 이름에 대한 hash(part) 값을 key로, 이름 part을 value로 하여 삽입
    • temp에 각 hash(part) 값들을 더해나감
  • 다시 completion 을 순회하며, temp 최종본에서 hash(com) 값들을 빼나감
  • 마지막에 temp 에 해당하는 값을 key로 하는 dic[temp] value 값을 리턴하면 남아있는 지원자의 이름을 반환하는 것과 같음
• 첫번째 반복문에서는 2n , 두번째 반복문에서는 n 이 걸리므로 총 시간 복잡도는 3n 이다.
• def solution(participant, completion): answer = '' temp = 0 dic = {} for part in participant: dic[hash(part)] = part temp += int(hash(part)) for com in completion: temp -= hash(com) answer = dic[temp] return answer

 

답안 코드 3

• 해시를 사용하지 않고 sort()를 이용해 이름을 정렬 후, 하나씩 비교하며 이름이 맞지 않는 경우 해당 선수가 완주하지 못했다고 판단하여 리턴
  • 문제의 의도와는 다르나, 시간 복잡도 측면에서는 효율적인 코드 구현
• 파이썬의 기본 정렬 함수 sort()는 기본적으로 평균적으로 nlogn, 최악인 경우에도 nlogn 을 보장해므로, 완주하지 못한 선수가 리스트의 가장 마지막에 있다고 치더라도 전체 시간 복잡도는 nlogn + n 에 불과하다.
• def solution(participant, completion): participant.sort() completion.sort() for i in range(len(completion)): if participant[i] != completion[i]: return participant[i] return participant[len(participant)-1]

 

---

리뷰

• 해시 문제를 입문하고 이해할 수 있었던 기본 문제
• Collections 모듈의 Counter

    counter1 = Counter(["A", "A", "B"])
    counter2 = Counter(["A", "B", "B"])
  
    # 두 Counter 객체 더하기
    print(counter1 + counter2) # Counter({'A': 3, 'B': 3})
  
    # 두 Counter 객체 빼기
    print(counter1 - counter2) # Counter({'A': 1})

  • 뺄샘의 결과로 0이나 음수가 나온 경우에는 최종 카운터 객체에서 제외가 됨
• 파이썬 collections 모듈의 Counter 사용법