프로그래머스 - '완주하지 못한 선수' [코딩테스트 고득점 Kit]

# 완주하지 못한 선수(해시) # 42576번 #lv1

 

# 문제

---

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

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

 

# 제한사항

---

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

 

#풀이

---

이 문제는 특이하게도 시간 제한과 효율성을 고려해야 하는 있는 문제라 첫 번째 풀이가 테스트에선 통과했음에도 답안에는 적절하지 않은 풀이였다.

# 풀이1

 # 1번 풀이
 
 def solution(participant, completion):
 
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        # participant - completion = 1 non complete
        participant.remove(completion[i])
    return participant[0]
    
    # 중복 요소 고려 필요
    # 차집합으로 구현? -> 그냥 remove 함수로 participant 내부 요소들을 삭제하면 안되나??
    # But, list 내부를 하나씩 돌리면서 찾으면 시간 오버되는 문제 발생.
    
 """ 
 1) 우선 두 리스트의 원활한 비교를 위해 모두 sorting을 해주었다.
 2) for 반복문을 이용해 completion 내부의 원소들이 participant에 들었는지 확인하고자 했으나 굳이..? 라는 생각이 들었다.
 > 어차피 sorting 되어있으므로 그냥 completion[i]가 participant 내부에 들어있다면 remove() 하는 방식
 3) 최종적으로 남은 participant 리스트의 첫 번째 요소를 return 한다.
"""

 

# 풀이2

 # 2번 풀이
 
 def solution(participant, completion):
 
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
    	# participant[i]와 completion[i]가 다를 시 바로 해당 인덱스의 participant 원소를 return.
        if participant[i] != completion[i]:
            return participant[i]
    # participant의 마지막 원소를 return        
    return participant[-1]
    
    
        # 왜 for 문 내부에도 return 구문이 있냐?
        # sort 된 리스트에서 다른 값이 있다는 건, 동명이인이 있다는 걸 의미. 
        # 동일 인덱스의 원소가 다르다는 건 해당 동명이인이 완주하지 못함을 의미함.
        
""" 
1) sorting 과정은 동일.
2) for 문을 통해 completion 내부 원소들을 하나씩 찾아내는 것도 동일하나, remove를 하지 않는다는 점에서 차이가 있다.
3) 만약 동일 인덱스 값의 completion, participant 원소들이 같다면 pass, 다르면 바로 해당 인덱스의 원소를 return.
> 만약 completion의 모든 인덱스에서 participant와 같다면 for문이 종료.
4) 앞 원소들의 값이 모두 같으므로, participant의 마지막 원소인 participant[-1]을 return 한다.
"""

 

> 해쉬를 이용해 문제를 풀진 않았지만, 내부 논리 구조가 정렬로도 풀 수 있는 방식이어서 생각보다 수월하게 문제를 풀었다. 그래도 다음에는 해시로 풀어봐야지..!