2019.04.21 TIL

프로그래머스 알고리즘 문제 (lv1)

• 완주하지 못한 선수

문제 설명

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

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

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다.

예시

나의 풀이 방법

의식의 흐름

1. 먼저 participant와 completion이 주어지는 것을 확인했다.
2. 내가 만약에 이 문제를 그냥 푼다고 하면 completion의 한명씩 가지고 와서 participant에서 찾아서 X표를 하나씩 할 것이다.
3. 그리고 마지막에 participant에서 지워지지 않은 사람을 이야기한다.

컴퓨터에게는?

1. 컴퓨터에게는 for문으로 completion을 돌면서 해당 요소를 participant에서 지우고 마지막에 participant를 반환하도록 할 것이다.
2. 추가적으로 그냥 반환하면 li를 반환하게 될 것이므로 문제에서 요구한 string으로 반환하게 해준다.

코드

def solution(participant, completion):
    for i in completion:
        participant.remove(i)
    print(participant[0])  #string으로 반환을 위해
    return participant[0]

• li의 특정요소를 지우기 위해 remove 함수를 사용하였다.
• print와 return 2개를 모두 적어주어 실제로도 볼 수 있도록 하였다.
• 첫 번째 인덱스를 반환하게 해주어 string으로 반환해주었다.
  • 현재 문제에서는 불완주자가 1명밖에 없지만 더 많은 불완주자가 있다고 하면 결과값 participant의 for문을 다시 돌면서 print하도록 해주어야 한다.

def solution(participant, completion):
    for i in completion:
    	participant.remove(i)
    for j in participant:
    	print(j)

다른 사람 풀이

import collections


def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

• remove는 효율이 굉장히 좋지 않다고 한다.

remove의 time complexity는 O(N)이에요. for 문과 합치면 이 코드의 time complexity는 O(N2)이에요.

시간 복잡도가 너무 높아서, 지금 코드로는 효율성 테스트케이스를 통과할 수 없을 겁니다 ㅜㅜ 시간 복잡도를 O(N)까지 줄여보세요.

• counter 함수에 대해서 새롭게 배우게 되었다.