[프로그래머스][LV.1] 완주하지 못한 선수 | python3

문제링크:  완주하지 못한 선수

---

문제설명

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

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

제한조건

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

---

 

문제풀이

아놔 에전풀이 백업 안함...ㅠㅜ

다행히 프로그래머스가 저장해줌...ㅎ

ㅇㅖ전풀이

def solution(participant, completion):
    pa_dic = {}
    final = participant + completion

    for i in final:
        if i not in pa_dic:
            pa_dic[i] = 1
        else:
            pa_dic[i] += 1

    for i in pa_dic.keys():
        if pa_dic[i] % 2 != 0:
            return i

def solution(participant, completion):
    answer = ''
    participant=list(set(participant))
    completion=list(set(completion))
    
    answer=participant+completion
    # answer=set(answer)
    print(answer)
    return answer

이런식으로 풀려고 했는데 동명이인일 경우를 걸러내지 못함.

 

예전풀이 옮기는 중에 풀이 방법 봐버림...

다른 방법으로 풀려고 노력했으나 생각나는 방법이 없어서 결국 비슷하게 풀었다...

 

딕셔너리에 넣어서 이름 나올때마다 1씩 더함. participant와 completion 둘 다 있어야 완주한 것이기 때문에 2로 안나눠지면 완주를 못한 것.

나의코드

def solution(participant, completion):
    names={}
    # completion 먼저 딕셔너리에 넣고 participant 원소와 비교하면서 없는 값을 리턴할까 했는데
    # 동명이인이 있기때문에 2로 나누는 방법으로 가야함
    total=participant+completion
    for name in total:
        if name in names:
            names[name]+=1
        else:
            names[name]=1
            
    for name in names.keys():
        if names[name]%2!=0:
            return name

 

---

 

참고하기

import collections

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

---

1. collections 모듈의 Counter 사용

import collections

• collections 모듈을 가져옵니다.
• 이 모듈에는 Counter라는 클래스가 포함되어 있는데, 리스트의 요소 개수를 쉽게 세는 기능을 제공합니다.

---

2. 함수 정의 및 Counter 적용

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)

• Counter(participant)는 참가자 리스트의 각 이름이 몇 번 등장했는지 세어 딕셔너리 형태로 저장합니다.
• Counter(completion)은 완주자 리스트의 이름 개수를 세어 저장합니다.
• 두 Counter 객체를 뺄셈(-) 연산하면 차이가 나는 요소만 남게 됩니다.
  (즉, 참가했지만 완주하지 못한 사람이 남음)

예제 분석

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]

위 데이터를 Counter로 변환하면:

collections.Counter(participant)  # {'leo': 1, 'kiki': 1, 'eden': 1}
collections.Counter(completion)   # {'eden': 1, 'kiki': 1}

이제 뺄셈을 수행하면:

collections.Counter(participant) - collections.Counter(completion)
# 결과: {'leo': 1}  (완주하지 못한 사람)

즉, "leo"만 남습니다.

---

3. 결과 반환

return list(answer.keys())[0]

• answer는 Counter 객체이므로, keys()를 호출하면 남은 선수들의 이름을 가져올 수 있습니다.
• 리스트로 변환한 뒤 첫 번째 요소를 반환하여 완주하지 못한 선수의 이름을 정답으로 반환합니다.

---

4. 전체 코드 실행 예제

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]

print(solution(participant, completion))  # "leo"

결과적으로 "leo"가 출력됩니다.

---

5. 동작 방식 정리

1. participant에서 등장 횟수를 센 Counter 객체를 만든다.
2. completion에서 등장 횟수를 센 Counter 객체를 만든다.
3. 두 객체를 뺄셈(-) 연산하면 완주하지 못한 사람만 남는다.
4. 남은 키 값 중 첫 번째 값을 반환한다.

이 코드는 시간 복잡도가 O(N) 이므로, 참가자 수가 커도 빠르게 동작할 수 있는 효율적인 방법입니다. 😊

 

---

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

 

해시로 푸는 게 이렇게 푸는거구나.

해시 함수(hash())를 사용하여 참가자의 데이터를 저장하고 비교하는 방식

---

1. 함수 및 변수 초기화

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}

• answer = '': 최종적으로 완주하지 못한 사람의 이름을 저장할 변수입니다.
• temp = 0: 참가자들의 해시 값의 합에서 완주자들의 해시 값을 빼서 완주하지 못한 사람의 해시 값을 찾는 변수입니다.
• dic = {}: 참가자들의 해시 값을 키(key)로 하고, 이름을 값(value)으로 저장할 딕셔너리입니다.

---

2. 참가자 목록을 dic에 저장하고 temp 계산

for part in participant:
    dic[hash(part)] = part
    temp += int(hash(part))

• hash(part): 참가자의 이름을 해시 값으로 변환합니다.
• dic[hash(part)] = part: 참가자의 해시 값을 키(key), 이름을 값(value)으로 딕셔너리에 저장합니다.
• temp += int(hash(part)): temp에 참가자의 해시 값을 더합니다.

예제 분석

participant = ["leo", "kiki", "eden"]

해시 값을 예제 값으로 가정하면:

hash("leo") = 123456
hash("kiki") = 789012
hash("eden") = 345678

그러면 dic의 상태는:

dic = {
    123456: "leo",
    789012: "kiki",
    345678: "eden"
}

그리고 temp 값:

temp = 123456 + 789012 + 345678  # 1258146

---

3. 완주자 목록을 temp에서 빼기

for com in completion:
    temp -= hash(com)

• 완주자의 해시 값을 temp에서 빼줍니다.
• 이렇게 하면 완주하지 못한 사람의 해시 값만 남게 됩니다.

예제에서 완주자가 "eden"과 "kiki"라고 하면:

temp -= hash("eden")  # temp = 1258146 - 345678 = 912468
temp -= hash("kiki")  # temp = 912468 - 789012 = 123456

즉, temp에는 "leo"의 해시 값만 남습니다.

---

4. 남은 해시 값을 이용해 정답 찾기

answer = dic[temp]

• dic에서 temp에 해당하는 값을 찾아 반환합니다.
• 예제에서는 dic[123456]을 찾으면 "leo"가 나오게 됩니다.

---

5. 최종 코드 실행 예제

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]

print(solution(participant, completion))  # "leo"

출력 결과:

leo

---

6. 동작 방식 정리

1. 참가자 이름을 hash()를 이용해 딕셔너리 dic에 저장.
2. 모든 참가자의 해시 값을 temp에 더함.
3. 완주자의 해시 값을 temp에서 빼서 완주하지 못한 참가자의 해시 값만 남김.
4. dic[temp]에서 해당 해시 값에 대응하는 이름을 찾아 반환.

📌 장점

• 딕셔너리 사용(O(1) 조회 가능) → 매우 빠름.
• 해시 값 사용 → 문자열 비교보다 효율적.

❗ 주의할 점

• hash() 함수는 Python 실행마다 결과가 달라질 수 있음 (Python 3.3+ 버전에서는 보안상 랜덤 시드가 적용됨).
• 다행히 hash()는 같은 실행 환경에서는 같은 값이 나오므로, 문제 해결에는 큰 영향이 없습니다.

이 방식은 O(N) 시간 복잡도로 매우 효율적입니다! 🚀

---

코드를 보면 hash(part)를 int(hash(part))로 변환하는 부분이 있습니다.
하지만 실제로는 hash(part)만 사용해도 됩니다.
hash() 함수 자체가 정수 값을 반환하므로 int()로 변환하는 것은 불필요합니다.

기존 코드

temp += int(hash(part))  # 불필요한 변환

개선된 코드

temp += hash(part)  # 그대로 사용해도 됨

이렇게 해도 동일하게 동작합니다.

---

❓ hash()는 원래 정수인가?

네! Python의 hash() 함수는 이미 정수 값을 반환합니다.

print(hash("leo"))  # 예: 123456789012345678
print(type(hash("leo")))  # <class 'int'>

따라서 int(hash(part))는 불필요한 변환입니다. 🚀