티스토리 뷰
[Python]프로그래머스 문제풀이 - 완주하지 못한 선수 찾기
서문
개발을 꿈꾸는 많은 분들이 기업에 취업하기 위해서 코딩테스트를 준비합니다. 코딩테스트란 기업에서 중요하다고 생각하는 알고리즘이나 논리를 코딩문제로 제출하고 지원자는 그 문제를 풀어서 코딩하는 실력뿐만 아니라 논리력과 표현력 등을 측정합니다.
또한 기업마다 중요시 하는 알고리즘과 문제유형들이 있을텐데 예컨대 로드맵을 만드는 기업이라면, 길 찾기 알고리즘을 많이 냅니다. 이런 식으로 어느정도 기업마다 유형이 나뉘어 있는데 이를 찾아서 집중적으로 풀어본다면 좋은 성적을 이룰 수 있습니다.
코딩테스트를 준비하기 위한 좋은 사이트들 중에 프로그래머스에서는 수많은 문제유형들을 분석하여 많이 출제되는 유형을 묶어서 제공하기 때문에 사용하는 이용자로 하여금 편리함을 제공합니다.
자 이제 한 문제씩 같이 풀어보도록 해요😀
- 프로그래머스 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42576
코드의 전개 논리가 궁금하시다면, 밑의 사이트에 들어가서 코드를 작성하여 visualize해주시면 코드가 어떤 식으로 흘러가는지 눈으로 파악하실 수 있습니다!
- 파이썬 튜터 사이트 : http://pythontutor.com/visualize.html#mode=display
1. 문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
2. 제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
3.입출력 예시
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"
본문
요약
참가자 선수의 배열과 완주자 선수의 배열이 주어진다.
완주하지 못한 선수의 이름을 return해라.
**참가자 인원의 제한은 1명 이상 100,000명 이하
참가자 이름은 1개 이상 20개 이하의 알파벳 소문자
**동명이인이 존재할 수 있다.
- 여기서 눈여겨 봐야할 점은 인원 제한이 10만명 이하 라는 점입니다. 기본적으로 이중 for문을 사용하여 풀스캔을 하면 시간복잡도가 O(n2) 이기 때문에 사용할 수 없습니다. 딕셔너리를 사용하면 시간복잡도가 O(n)이기에 10만명이라고 해도 가능합니다.
- 간단하게 생각하면 참가자에서 완주한 선수를 제거하면 완주하지 못한 선수가 남으니까 쉽다고 생각할 수 있지만, 5번 제한인 동명이인을 처리해야합니다.
문제 풀이
- 1번 풀이
participant = ["mislav", "stanko", "mislav", "ana"]
completion = ["stanko", "mislav", "ana"]
def solution(participant,completion):
answer = ''
# 1
dict_list = {}
for i in participant:
if i not in dict_list.keys():
dict_list[i] = 0
if i in dict_list.keys():
dict_list[i] += 1
# 2
for j in completion:
if j in dict_list.keys():
dict_list[j] -= 1
# 3
for n in dict_list.keys():
if dict_list[n] > 0:
answer = n
return answerDetail Code Review
- 참가자 선수를 딕션의 key로 넣을텐데 만약에 딕션에 선수의 이름이 없다면 value를 0으로해서 초기화합니다. 만약에 딕션에 선수의 이름이 있다면
+1을 해줍니다.
- 예를 들어
participant = ["mislav", "stanko", "mislav", "ana"]라면dict_list ={"mislav" : 2, "stanko" : 1, "ana" : 1}이 됩니다. 즉 두명은 2로 처리되고 한명은 value가 1이 됩니다.
- 완주자 선수의 리스트를 돌면서 만약 dict_list에 완주자 선수의 이름이 있다면
-1을 해줍니다.
- 그 결과 ``dict_list ={"mislav" : 1, "stanko" : 0, "ana" : 0}` 입니다.
- 결론적으로 value값이 0 초과하는 값이 있으면 그것을 뽑으면 완주하지 못한 선수가 됩니다.
- 2번 풀이 (collection이라는 python 라이브러리를 활용한 풀이)
import collections
part = ['mislav', 'stanko', 'mislav', 'ana']
comp = ['stanko', 'ana', 'mislav']
print(collections.Counter(part))
# Counter({'mislav': 2, 'stanko': 1, 'ana': 1})
print(collections.Counter(comp))
# Counter({'stanko': 1, 'ana': 1, 'mislav': 1})
print(collections.Counter(part) - collections.Counter(comp)) # mislav이 문제 풀이는 제가 한 방법이랑 거의 똑같습니다. 코드효율측면에서는 더 좋을 것 같네요~~ 😊
- 3번 풀이 (hash()함수를 사용한 풀이)
participant = ['mislav', 'stanko', 'mislav', 'ana']
completion = ['stanko', 'ana', 'mislav']
# participant
mislav hash 값 : -4823864767795648272
stanko hash 값 : 7853276010511331364
mislav hash 값 : -4823864767795648272
ana hash 값 : -6313150445889359294
# completion
stanko hash 값 : 7853276010511331364
ana hash 값 : -6313150445889359294
mislav hash 값 : -4823864767795648272 이를 이용하여 key에 각 주소를 value에 각 이름을 넣은 뒤 서로의 합을 뺀 수를 키 값으로 넣어주면 value값인 이름을 뽑을 수 있습니다.
sum1 = 0
dict_list = {}
for part in participant:
dict_list[hash(part)] = part
sum1 += int(hash(part))
for com in completion:
sum1 -= hash(com)
print(dict_list[sum1])
지금까지 완주하지 못한 선수 라는 문제를 풀어봤습니다.
아직 코드에 익숙하지 않고, 논리적인 생각을 코드로 풀어내기 위해서 많이 노력해야겠습니다😥 혹시 코드에 오류나 효율적이지 못한 부분 있으면 알려주세요~😂
마치 영어나 중국어를 수없이 해서 자신의 생각을 자연스럽게 풀어내는 것처럼 먼 훗날에 코드로도 제 생각을 쭉 풀어내는 그 날이 오길 기다리며...
감사합니다😁
