문제:

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

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

풀이 방법:

해시를 사용해서 푸는 문제이므로 Python의 set의 특징을 이용한다면 쉽게 풀 수 있었다. Python에서의 set은 중복을 제거해주고, 차집합과 같은 연산도 지원을 해주었다. set을 통해서 중복을 제거할 수 있다는 특징을 이용해서 동명이인이 완주를 못 한 사람인지 아닌지를 판단 할 수 있다. 두 개의 배열에 set을 취한 뒤 차집합을 해주었을 때, 1이라면 동명이인이 범인이 아닌경우이며, 0이라면 동명이인이 범인인 경우이다.
따라서 이를 판별하기 전에 각각의 배열을 정렬해준 뒤에 차집합의 길이가 1이라면 두 개의 차 집합에서 남은 사람이 완주를 하지 못한 사람이며, 0일 경우에는 하나씩 탐색했을 때 서로 다른 부분에서 완주를 하지 못한 사람을 찾을 수 있다.

1
2
3
4
5
6
7
8
9
10
def solution(participant,completion):
    participant.sort()
    completion.sort()
    if not bool(set(participant)-set(completion)):
        for i in range(len(completion)):
            if participant[i]!=completion[i]:
                return participant[i]
    else:
        answer=list(set(participant)-set(completion))[0]
    return answer
cs


'Algorithm' 카테고리의 다른 글

[BOJ]11559. Puyo Puyo  (0) 2021.09.07
[BOJ]3190. 뱀  (0) 2021.08.19
[BOJ]1520. 내리막길  (0) 2021.08.17
[BOJ]1987. 알파벳  (0) 2021.08.10
[BOJ]14425. 문자열 집합  (0) 2021.06.24

+ Recent posts