42576: 완주하지 못한 선수[해시]

Link : programmers.co.kr/learn/courses/30/lessons/42576

---

1. 문제

• 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
  마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

---

2. 문제의 조건

• 1 <= N <= 100,000
• 1 <= name <= 20

 

---

3. 문제 접근

• 시간 복잡도
  
  제한시간 1초, 10만개의 데이터입니다. O(N^1.6)시간 내에 풀면 가능합니다.

 

• 아이디어
  
  dict을 이용하여 participant를 전부 등록하고 completion을 빼준다음 남은 데이터 중 1보다 크면 완주를 못한 사람이므로 출력합니다.
  
  즉, dict을 이용하여 O(N)에 해결이 가능합니다.

 

---

4. 풀이 방법

• 들어온 데이터를 dict에 등록해준다. (값 = 1)
• 완주자 목록을 들어온 데이터에서 빼준다
• 데이터 중 1 이상인 사람이 있으면 완주를 못한 사람이므로 출력하면됩니다.

 

---

5. 소스코드

• cjw-git.tistory.com/77

 

---

 

cjw.git@gmail.com