[프로그래머스/해시] 포켓몬 , 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

 

📌 문제 

 

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

 

📌 아이디어 

 

같은 종류의 포켓몬을 선택하는 것은 최대값이 아니다. 

따라서 pocketmon 종류를 set을 활용하여 중복을 없애준다. (set은 순서가 없고, 중복을 허용하지 않는다.) 

가져갈 수 있는 포켓몬의 수 보다 포켓몬의 종류가 작을 때는 포켓몬의 종류가 정답이 되고, 

가져갈 수 있는 포켓몬의 수가 포켓몬의 종류보다 작을 때는 가져갈 수 있는 포켓몬의 수가 정답이 된다. 

 

예를 들어서 가져갈 수 있는 포켓몬의 수가 2개인데 , 포켓몬의 종류가 3가지일 때는 최대로 가져갈 수 있는 포켓몬의 종류수는 2개가 되는 것이고, 가져갈 수 있는 포켓몬의 수는 4개 인데, 포켓몬의 종류는 3가지인 경우에는 최대로 가져갈 수 있는 포켓몬의 종류의 최대값은 3이 된다. 

 

📌 코드 

def solution(nums) :
	num = len(nums) // 2 #가져갈 수 있는 포켓몬 수 
    pocketmon = set(nums) #포켓몬 종류 
    answer = min(num , len(pocketmon) ) #두 수 중 min 값이 가져갈 수 있는 최대 종류 수 
    return answer

 

---

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

프로그래머스

 

📌문제 

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

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

제한사항

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

📌아이디어 

단 한명의 선수를 제외하고 모든 선수가 마라톤을 완주하므로 (참가자 - 완주선수) 를 활용해서 완주하지 못한 선수를 찾으면 된다. 

처음에는 리스트끼리 빼는 방법을 사용했는데, 알고보니 리스트끼리 덧셈은 가능하지만 뺄셈은 지원하지 않는다는 것을 알게  되었다. 

그렇다면 for문을 활용해서 만일 완주자 명단에 있을 경우 제거하는 코드를 작성하면 되겠다!! 했지만,  동명이인도 함께 제거되는 결과가 나왔다. (당연한 결과..)  

약간의 힌트를 얻어 파이썬의 collections 모듈의 Counter 클래스를 사용했다. (데이터 개수를 셀 때 매우 유용하다) 

 

Counter 

https://docs.python.org/ko/3/library/collections.html#collections.Counter

collections — Container datatypes

 

• Counter 생성자는 여러 형태의 데이터를 인자로 받는다. 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지 저장된 객체를 얻게 된다. 
• 덧셈, 뺄셈 모두 가능하다. 단, 뺄셈의 결과로 0이나 음수가 나온 경우에는 최종 Counter 객체에서 제외가 된다, 
• 사전(Dict) 처럼 활용할 수 있다. 즉, 대괄호를 이용하여 키로 값을 읽을 수 있고 특정 키에 해당하는 값을 갱신할 수 있다.  

📌코드 

from collections import Counter

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