오늘 풀어본 문제는 프로그래머스에 있는 완주하지 못한 선수라는 문제입니다.


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



이 문제에 대해 간단히 설명을 하자면


마라톤에 참여한 선수들의 이름 리스트가 있고, 그 중 완주한 선수들의 이름 리스트가 있습니다.


완주하지못한 선수는 단 1명 뿐입니다. 그러므로 참여선수리스트와 완주한 선수들의 리스트의 길이 차는 1입니다.



참가자 중에는 동명이인이 있습니다.



먼저, 해당 문제에서는 어떤 자료구조를 선택해서 문제를 해결하느냐가 핵심일 것 같습니다.


생각해본 문제 풀이 방법은


1) 정렬을 해서 비교하면 다른 원소일 때 해당 값을 리턴 하는 방법. 정렬하는데 O(nlogn)의 시간이 소요되는데 리스트가 2개이고 또 마지막에 순회할 때 O(n) 의 시간복잡도가 필요하기 때문에 좋은 방법이라고 생각하지 않았습니다.


2) 해쉬 자료구조를 사용해서 이름을 키로 사용한 후에 해당 키에 접근에서 빼는 방식으로 하면 O(n) 의 시간복잡도를 2번 필요로 하기 때문에 위에 방법보다 더 좋은 방법이라고 생각했습니다.




제가 작성한 코드입니다.


먼저 완주한 선수 리스트를 dictonary에 넣어준 후에


참가자리스트에 있는 선수들을 나온 순서로 체크해서 이미 해당 값의 key의 value가 0이 되거나 value이 없는경우 해당 key 를 리턴해주도록 작성하였습니다.




복사 가능한 코드


def solution(participant: list , completion:list ) -> str:

    dictionary = {}

    for v in completion:

        if dictionary.get(v):

            dictionary[v] +=1

        else:

            dictionary[v] = 1

    

    for v in participant:

        if dictionary.get(v):

            if dictionary == 0:

                return v

            else:

                dictionary[v] -=1

        else:

            return v

        

    return answer



다른 분이 작성한 코드 중에서 파이썬이 collections 패키지의 Counter 를 사용해서 문제를 해결한 분이 있어서 소개드리려고 합니다.


collections 패키지는 파이썬에서 제공하는 강력한 컨테이너 데이터 타입입니다.


그 중에서 Counter는 hashable 객체의 카운팅을 위한 Dict의 서브클래스입니다. 


즉, 위에서 제가 dictonary를 사용해서 해당 키의 빈도를 counting한 경우에 사용하면 딱인 데이터 타입입니다.




이런식으로 리스트를 이용해서 생성하면 다음과 같이 dictionary가 만들어집니다.



Counter 를 사용한 코드입니다.




코드가 보다 간결해진 것을 확인할 수 있습니다.



문제를 풀다 보면 다양한 방법으로 푼 다른 분들의 

코드를 볼 수 있어서 많이 도움이 됩니다.


혹시, 잘못된 부분이 있거나 궁금하신점이 있으면 댓글 남겨주세요.


감사합니다.





+ Recent posts