프로그래머스 해시 함수 마라톤 문제를 푸는 3가지 과정에 대해 정리해보려 한다.
나는 원래
문제 설명
여러 명의 마라톤 선수들이 참가하였고, 그 중 하나만이 완주하지 못했습니다. 두 개의 배열, participant와 completion이 주어질 때, 완주하지 못한 선수의 이름을 반환하는 함수를 작성하라.
예를 들어, 다음과 같은 입력이 있을 수 있습니다:
participant = ["mike", "john", "sara", "mike"] completion = ["mike", "john", "mike"] 이 경우, "sara"가 완주하지 못한 선수입니다.
방법 1: Counter 사용하기
Python의 collections 모듈에 포함된 Counter 클래스를 활용하면 문제를 간단히 해결할 수 있습니다. Counter는 주어진 iterable의 요소 개수를 세어주는 유용한 도구입니다.
from collections import Counter
def solution(participant, completion):
answer = Counter(participant) - Counter(completion)
return list(answer.keys())[0]-
Counter 생성: Counter(participant)는 participant 배열의 각 이름과 그 개수를 세어줍니다. 예를 들어, 위의 예시에서 Counter(participant)는 {'mike': 2, 'john': 1, 'sara': 1}의 결과를 반환합니다.
-
차집합 계산: Counter(participant) - Counter(completion)은 participant에서 completion에 포함된 선수들을 제거한 결과를 반환합니다. 만약 completion 배열에 없는 선수인 "sara"만 남게 됩니다.
-
결과 반환: list(answer.keys())[0]를 사용하여 완주하지 못한 선수의 이름을 반환합니다.
방법 2: 해시 테이블 사용하기
해시 테이블을 활용한 두 번째 방법도 소개하겠습니다. 이 방법은 주어진 배열을 순회하면서 각 선수의 이름을 세는 방식입니다.
def solution(participant, completion):
participant_dict = {}
for person in participant:
if person in participant_dict:
participant_dict[person] += 1
else:
participant_dict[person] = 1
for person in completion:
participant_dict[person] -= 1
for person, count in participant_dict.items():
if count > 0:
return person-
딕셔너리 생성: participant_dict를 생성하여 각 선수의 이름과 그 개수를 저장합니다.
-
완주한 선수 처리: completion 배열을 순회하면서, 완주한 선수의 카운트를 감소시킵니다.
-
결과 확인: 마지막으로 카운트가 0보다 큰 이름, 즉 완주하지 못한 선수를 반환합니다.
방법 3: 정렬을 이용한 방법
정렬을 통해 해결하는 방법도 있습니다. 이는 두 배열을 정렬한 후, 한 요소씩 비교하여 완주하지 못한 선수를 찾는 방식입니다.
def solution(participant, completion):
participant.sort()
completion.sort()
for i in range(len(completion)):
if participant[i] != completion[i]:
return participant[i]
return participant[-1]- 정렬: participant와 completion 배열을 각각 정렬합니다.
- 비교: 두 배열을 순회하면서 첫 번째로 다른 선수 이름을 찾으면 그 선수를 반환합니다.
- 마지막 선수 반환: 만약 모든 요소가 같다면 마지막 선수, 즉 완주하지 못한 선수를 반환합니다.
시간복잡도를 생각했을 때 해시를 쓰는 것이 낫다. 하지만 코드의 복잡성을 생각했을 때는 Collection 속 Counter에 대해 알고 있으면 코딩테스트용 문제를 풀 때 쓸 일이 많은 것 같다. 물론 그 둘도 아닌 정렬을 이용한 방식을 먼저 생각해낸 나는 더 열심히 코딩테스트 공부를 해야할 듯 싶다.
