[python] 완주하지 못한 선수(해시)

문제는 위와 같다. 단 한 명의 완주하지 못한 선수를 찾아내는 것이 문제의 목표이다. 마라톤에 참여한 모든 선수의 이름이 담긴 배열 participant가 주어지고 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때 완주하지 못한 선수를 찾아내야 한다.

위와 같은 예시가 주어진다. ["leo", "kiki", "eden"] 라는 participant 배열과 ["eden", "kiki"] 라는 completion배열이 주어지면 참가한 선수 중에 completion배열에 들어있지 않은 "leo"라는 선수는 완주하지 못한 선수가 되므로 "leo"를 반환해주면 해당 문제가 해결된다.

 

설계 및 구현

구현을 위해 주어진 코드는 solution함수가 전부이다. 매개변수로는 participant, completion 배열을 받는다.

맨 처음 간단하게 생각해 보았을 때 참가한 선수 배열의 원소를 사용하여 completion배열에 count함수를 사용해서 0이 나온다면 완주하지 못한 것이기 때문에 해당 participant의 원소를 반환하면 된다고 생각했다.

일반적인 상황에서는 제대로 동작하지만 동명이인의 경우를 생각하지 못해 에러가 발생했다. 3번째 예제처럼 동명 이인중 한 명만이 완주를 했을 경우 

count자체에서 0이 나오지 않기 때문에 완주하지 못한 사람을 찾을 수 없는 오류가 발생하게 된다.

 

동명이인의 경우를 해결하기 위해 count와 비슷한 동작을 하는 collection모듈의 Counter를 생각했다.

Counter의 경우 컨테이너에 동일한 값의 자료가 몇개인지를 파악하는 데 사용하는 객체로 전달받은 컨테이너 내부의 원소를 확인하여 해당 원소의 값이 몇 번 등장했는지 파악하여 원소를 key로 등장 횟수를 value로 입력하여 딕셔너리로 반환해 준다. Counter객체의 경우 일반 딕셔너리와 다르게 산술 연산과 집합 연산이 가능하기 때문에 participant와 completion 배열을 사용해 생성한 Counter객체 간의 빼기 연산을 이용한다면 동일한 값의 원소의 경우 participant에 있는 원소의 개수에서 completion에 있는 원소의 개수가 연산을 통해 동일 횟수일 경우 0이 되어 사라지게 되고 수가 다르다면 원소가 남게 되어 동명이인의 문제가 해결되고 남은 원소는 자동으로 완주하지 못한 선수가 될 것이라고 생각했다.

동명이인이 존재하는 경우에도 participant로 생성한 Counter객체는 "mislav":2 로 completion를 사용해 생성한 Counter객체는 "mislac":1로 가지고 있고 빼기 연산을 수행하면 1이 남아 1명의 mislav라는 사람은 완주하지 못한 것으로 나오게 된다.

딕셔너리 형태로 반환되기 때문에 key값에 대한 list로 변환하고 완주하지 못한 선수는 1명이라고 정해져 있으므로 해당 리스트의 첫번째 인덱스가 완주하지 못한 선수가 된다.

설계한 대로 구현한 코드가 리스트의 사람이 많아지면 Counter객체를 생성하는데 시간이 오래걸려 효율성 테스트를 통과하기 애매하다고 생각했지만 다행히 테스트를 통과하였다.