세무민의 코딩일기 : 프로그래머스 완주하지 못한 선수 문제 풀기

이번에 풀어볼 문제는 완주하지 못한 선수!

이 문제는 생각해보면 쉽지만 효율성에서 통과하기 어려웠던 문제 중 하나

---

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,

완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

---

제한 사항 및 입출력 예시

[ 제한사항 ]

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

[ 입출력 예 ]

participant	completion	return
[leo, kiki, eden]	[eden, kiki]	leo
[marina, josipa, nikola, vinko, filipa]	[josipa, filipa, marina, nikola]	vinko
[mislav, stanko, mislav, ana]	[stanko, ana, mislav]	mislav

 [입출력 예 설명 ]

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

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

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

---

풀이

이 문제는 쉬운데 효율성에서 자꾸 실패했었다.

일단 말 그대로 participant에 존재하지 않는 completion을 찾으면 된다.

여기서 체크해야 할 부분은 같은 값이 존재할 수 있기 때문에 개수를 잘 체크해야 한다.

가장 중요한 포인트는 participant = Completion - 1

코드 리뷰에서 자세하게 설명해보겠다.

---

코드

#1 첫번째 접근

def solution(participant, completion):
    answer = ""
    i = 0
    while len(participant) > 1:
        count = i
        if completion[0] == participant[i]:
            participant.pop(i)
            i = 0
        elif count == len(participant) - 1:
            tmp = completion[0]
            completion.pop(0)
            completion.append(tmp)
            i = 0
        else:
            i += 1
    answer = (''.join(participant))
    return answer

처음 접근했을 땐 while문을 이용해서 participant를 하나씩 제거하여 

결국 마지막에 남는 값을 체크하는 방향으로 가려고 했으나

처참한 결과가 나를 반겨줬다 ㅋㅋㅋㅋㅋㅋㅋㅋ

#2 두번째 접근

   def solution(participant, completion):
    answer = ""
    participant.sort()
    completion.sort()
    
    
    for i in completion:
        participant.remove(i)

    answer = (''.join(participant))    
    return answer

두번째 접근은 완전 성공인 줄 ㅋㅋㅋㅋㅋㅋㅋ

사실 반복문을 사용해서 하나씩 비교하면서 존재한 값을 제거하던 방식을 

정렬하여 하나씩 찾아서 제거하는 방법을 구현했는데 

이렇게 생각한 이유는 

예를 들어서 A = [3,5,7,3] 과 B=[3,5,3] 을 가정해보면 

정렬하게 되면 A = [3,3,5,7], B = [3,3,5]가 되고 결국에는 빠르게 제거가 가능하기 때문에

굳이 while을 쓰지 않아도 되고 제거하다보면 인덱스 오차가 생기는 문제도 최소화 할 수 있을 것이라고 생각했다.

그러나 이번엔 효율성에서 실패 ㅋㅋㅋㅋㅋㅋㅋㅋ

이때 멘붕이 오지게 왔다.

#3 세번째 접근

def solution(participant, completion):
    answer = ""
	participant.sort()
    completion.sort()

    checkC = {}
    checkP = {}


    for i, v in enumerate(participant):
        checkP.update({v:participant.count(v)})

    for i, v in enumerate(completion):
        checkC.update({v:completion.count(v)})


    answer = ""    
    result = list(checkC.items())
    for i in checkP.items():
        if i not in result:
            answer = i[0]

    return answer

곰곰히 생각하다가 dict()을 이용해봤다.

딕셔너리를 이용해서 이름을 key, 이름의 개수를 value로 만들어서 

반복문에 존재하는지 여부를 확인하는 방식으로 했다.

처참한건 여전하다......

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

효율성을 맞추는게 참 어렵다.

효율성을 생각하다보니 고민하게 된 부분은 

시간복잡도!

반복문을 사용하는 경우 대부분 O(N) 시간이 소요되는데 

만약에 이중포문이나 remove와 같은 매소드를 이용한다면 O(n)보다 더 많은 시간이 소요된다는 점....

그래서 고민하다가 participant = Completion - 1 이라는 것이 생각났다.

결국에 정렬된 값에서 일치하지 않는 값이 존재한다면 

그 일치하지 않는값이 결국에는 존재하지 않는 값이라는 생각이 들었고 

만약에 completion과 일치한다면 Participant에 마지막 값이 존재하지 않는 값이 될 것이라는 생각이 들었다.

#Final 완성 코드

def solution(participant, completion):
    answer = ""
    participant.sort()
    completion.sort()

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

하나씩 비교해줘서 틀린 값을 찾아주거나 일치한다면 마지막 값을 호출해주는 방식으로 구현하면 

결국 O(N)시간이 소요되기 때문에 효율성에서도 큰 무리가 없다.

끝!

---

코딩 공부를 더 열심히 해야겠다는 생각 뿐이다..

다음에는 더 좋은 포스팅으로 찾아오겠습니다.