완주하지 못한 선수

https://programmers.co.kr/learn/courses/30/lessons/42576

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

문제 설명

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

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

제한사항

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

입출력 예

 

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

def solution(participant, completion):
    answer = ''
    for i in completion:
        participant.remove(i)
    for j in participant:
        answer += j
    
    return answer

이렇게 하면 테스트는 통과하지만 

효율성의 문제가 생긴다. 

다시 풀어보자 아마 for 문이 너무 많아서 문제 같다.

 

def solution(participant, completion):

    for i in completion:
        participant.remove(i)
    answer = ''.join(participant)

    return answer

아래의 for 문을 바꿔 보았다. 하지만 그래도 효율성의 문제가 생긴다. 

리스트를 문자열로 바꾸는 방법을 찾아서 생각해봤다.

A = ["a", "b", "c"]
StrA = "".join(A)
print(StrA)

join 메소드는 임의의 수의 문자열을 연결하며, 메소드가 호출 된 문자열은 주어진 각 문자열 사이에 삽입됩니다. 예제에서 볼 수 있듯이 빈 문자열 인 문자열 ""은 목록 요소 사이에 삽입됩니다.

요소 사이에 공백을 추가하려면 다음을 사용해야합니다.

www.delftstack.com/ko/howto/python/how-to-convert-a-list-to-string/

파이썬에서리스트를 문자열로 변환하는 방법

아마도 위의 for 문이 문제인거 같다.... 

흠....

 

def solution(participant, completion):

    a=set(participant)-set(completion)

    answer = ''.join(a)

    return answer

이렇게 하니 몇 몇 테스트는 안되나 효율성은 올라갔다 그이유는 set()함수가 중복을 허락하지 않기 때문

 

remove()함수의 시간복잡도는 O(N)입니다. 위의 for문과 합치면 작성자님의 코드의 시간복잡도는 O(N2)이 되겠네요. O(N)으로 해결할 수 있는 방법을 생각해 보세요

 

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

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


    return participant[i+1]

이문제가 ㄹㅇ 개어려웠다....

여기서 문제의 특징을 잘 파악해야했다.  한명만 완주를 못한다... 근데 이거는 이 특정 경우만 허용하는 것이니..

우선 참고

import collections


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

다른 사람의 풀이이다.

여기서 collections 의 counter 을 잘 알아보도록 하자...허허

collections.Counter()

컨테이너에 동일한 값의 자료가 몇개인지를 파악하는데 사용하는 객체이다.
docs.python.org에서 Counter함수에 대해 자세히 알아볼 수 있다.
excelsior-cjh.tistory.com/94

collections 모듈 - Counter

딕셔너리 의 집합 형태로 나오고 빼기를 해주고나면 남는것이 있가 그때 key의 값만 리턴해주먼 문제를 더 쉽게 해결 할 수 있다.