[파이썬] 코딩테스트 08 자료형_마라톤

문제

프로그래머스

 

---

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

---

풀이

• 기출 아님
  • 앞에 했던 것 들에 대한 단순 리뷰
  • 자주 사용되는 구조

---

• 문제
  • 입력 : 참가자들, 완주자들
  • 할 일 : 못 들어온 1명을 찾아주세요!

---

• 시도1) 아무 생각없이 하면
  • 완주자 명단을 돌아가면서 참가자 명단에서 지우면 됨
  • 동명이인을 구별하지 않아서 단순히 remove 사용하자 //////

    def solution(participant, completion):
        for name in completion: #완주자 명단 보면서
            #참가자 명단 보면서 한 명씩 지우자 
            participant.remove(name)
        return participant[0]
    ​

  • 최악의 경우를 생각하면 → 10만개를 지우려면 10만번을 맨 앞에서 쫙 훑어야하므로 →세상에나 비효율적이다~
  • p = [a,b,c,d] c = [d,c,b] 1+2+3+ … +N → N^2 비례!! ⇒ 참가자가 많을수록,,,,이 일을 하기에,,오래오래 걸린다!!

---

• 시도2) dict 구현 : key - value
  • 개수의 비례를 받지 않는다
  • 0(1) → Hash 알고리즘
  • 이 문제 세팅
    • dict = {이름 : 몇 명}
      • 단점 → 주어진 자료를 그대로 사용하면 안 되고 내가 이렇게 만들어야함
      • p = ["mislav", "stanko", "mislav", "ana"]
        • {"mislav" : 1} {"mislav" : 1 + 1 , "stanko":1, “ana” : 1} {"mislav" : 1 + 1 , "stanko":1, “ana” : 1}
        ⇒ {"mislav" : 2 , "stanko":1, “ana” : 1} → N의 복잡
      • 등록 과정의 이슈
        • 신규 등록 --> k(신규이름) : v=1
        • 기 등록 --> k(기등록) : v += 1 갱신
      • c = ["stanko", "ana", "mislav"] 이것으로 보면서 참가자 명단 제거
        • {"mislav" : 2 , "stanko":1 ,"ana":1}
          • stanko : {"mislav" : 2 , "ana":1}
          • ana : {"mislav" : 2 }
          • mislav : {"mislav" : 2-1 }
          ⇒ {"mislav" : 1}
          • 남은 dict의 키값 → 완주하지 못한 사람의 이름!!!!
      • 제거 과정 이슈
        • 완주자 이름으로 키 값을 조회!!! value ==1 : 삭제 value>=2 : 값-1갱신
      • 전체 과정의 복잡도
        • 참가자 명단 정리 : N 복잡도
        • 완주자 명단 정리 : N-1복잡도 == N복잡도 ⇒ 2N복잡도 ~~~ N복잡도 0(N) 

  • def solution (participant, completion):
        answer = ''
        #0.참가자 정보 처리할 변수 만들려고함 -> dict
        # k: 참가자 이름 , v: 이름에 대한 참가자 수
        p_dict = {}
    
        #1) 입력 참가자 명단을 보면서 정리 -> 롤링을 위한 for
        for p in participant:
            #참가자 1명씩 불러다가 내가 할 일
            #기준 : 기등록 이름인지, 처음 등록 이름인지
            if p in p_dict: # 기존의 등록된 이름인가?
                #기등록 이름
                p_dict[p] += 1
            else:
                #신규등록이름
                p_dict[p] = 1
        #--> 참가자 명단 dict로 정리/ 어떤 이름 : 몇 명 등록된 이름인지
        #0(N)
    
        #2)완주자 명단 롤링
        for c in completion:
            #완주자 1명씩 불러다가 할 일
            #기준 : 이름에 대한 사람 수가 1인지, 2명이상인지
            if p_dict[c] == 1:# 1명 참가 or 1명 남아있을지도
                del p_dict[c]
            else:# 아직 동명이인이 2명이상 남아있는 경우
                p_dict[c] -= 1
        #--> 완주자 명단을 보면서 dict의 값을 줄이기/삭제
        # 1명만 남게 됨
    
        answer = list(p_dict.keys())[0]
        return answer
    

  • 정리
    • 파이썬으로 가지고 여러개 값을 다루는 다양한 자료형
    • 각기 자료형마다 특징이 있다
    • list vs dict
      • 값에 대한 접근 방식
        • list → 순서적으로 쭉… 정수인덱스 사용
        • dict → key 중심으로 접근
      • 여러개 값들을 신규 등록..제거..
        • list → append, insert// pop, remove
        • dict → d[k]=v // del d[k]
      • 갱신
        • list → l[3] = 99
        • dict → d[k] = 99
      • list의 최악→ 맨 마지막 값을 쭉 찾기 위해서는 순회 dict는 key 중심으로 바로 접근 list : 0(N) vs dict : ~~0(1)
    • 결론
      • 파이썬을 가지고 코테를 푸는 과정에서 효율성 고민해야한다면⇒가장 손쉬운 방법 중 하나가 자료형 dict 사용하기!!!