[Problem Solving] 프로그래머스 42576 완주하지 못한 선수

 완주하지 못한 선수에 대한 문제 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명

코딩테스트 연습 - 완주하지 못한 선수

 

해당 문제는 참가자(participant)와 완주자(completion)가 주어지고, 단 한 명의 선수를 제외하고 모든 선수가 마라톤을 완주했다는 조건을 만족합니다. 따라서 정렬과 딕셔너리를 이용하여 문제를 해결할 수 있습니다.

 

다음은 정렬을 이용한 문제 해결 방법입니다.

1. 참가자 배열을 정렬한다.
2. 완주자 배열을 정렬한다.
3. index를 하나씩 돌어가며 index에 따른 참가자, 완주자 배열의 값을 비교한다.
4. 3의 값이 같다면 아무런 처리를 하지 않는다.
5. 3의 값이 다르다면 해당 index의 참가자가 완주하지 못한 선수이므로 결과로 반환한다.
6. 모든 index를 돌아본 후에도 결과가 반환되지 않았다면 마지막 선수가 완주하지 못한 선수이므로 결과로 반환한다.

다음은 정렬 해결 순서를 코드로 구현한 것입니다.

 

def solution(participant, completion):
  participant.sort()
  completion.sort()

  for i in range(len(completion)):
    if (participant[i] != completion[i]):
      return participant[i]
  return participant[len(participant)-1]

처음 참가자와 완주자의 값이 같지 않은 부분이 정답이 될 수 있는 이유는 한 명을 제외한 모든 선수가 마라톤을 완주했기 때문입니다.

 

다음은 딕셔너리를 이용한 문제 해결 방법입니다.

1. 참가자 배열값을 순환한다.
2. 딕셔너리에 1의 원소가 존재하지 않으면 key, value를 1의 원소, 1로 초기화해준다.
3. 딕셔너리에 1의 원소가 존재하면 해당 key의 value를 1 더 해준다.
4. 완주자 배열 값을 순환한다.
5. 딕셔너리에 4의 원소의 value를 -1 해준다.
6. 딕셔너리의 key, value를 순환하며 count가 0이 아닌 선수를 반환한다.

다음은 딕셔너리 해결 순서를 코드로 구현한 것입니다.

 

def solution (participant, completion):
  answer = []
  player_dict = {}

  for player in participant:
    if player in player_dict:
      player_dict[player] += 1
    else:
      player_dict[player] = 1

  for player in completion:
    player_dict[player] -= 1

  answer = [player for player, count in player_dict.items() if count != 0]
  return answer[0]

 

결괏값을 answer[0]으로 반환할 수 있는 이유는 한 명의 제외한 모든 선수가 마라톤을 완주하였기 때문에 answer 배열에는 값이 1개가 존재하고, 그것이 정답이라는 것이 보장이 되기 때문입니다.

 

딕셔너리를 사용하면 정렬로 해결하는 방법과는 다르게 여러 명이 완주하지 못한 상황에 대해서 조금 더 유연하게 대처할 수 있습니다.

 

정렬을 사용한 방법, 딕셔너리를 사용한 방법 모두 효율성 테스트를 통과하지만 계산된 시간을 비교해보았을 때 딕셔너리를 사용한 방법이 더 빨랐습니다. 아마 정렬을 사용한 방법은 O(nlogn)(정렬 시간)의 시간 복잡도를 가지고, 딕셔너리를 사용한 방법은 O(n)(참가자, 완주자 순환)의 시간 복잡도를 가지기 때문인 것 같습니다.

 

이번 문제는 처음에는 정렬을 이용하여 해결하였지만 추후 시간이 흐른 뒤에 해쉬로 접근하여 한번 더 해결을 하였습니다. 이렇듯 프로그래밍에는 여러 해결 방법이 존재합니다. 다른 방법으로 접근하여 해결하는 방법을 연습하는 것도 코딩 테스트 능력 향상에 있어 중요한 것 같습니다.