[프로그래머스/Python] 알고리즘고득점Kit-해시-폰켓몬

📌 문제 링크

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

프로그래머스

 

 

📌 문제 설명 

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

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

 

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

# 제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

 

📌 풀이 과정 

• 생각 1) n개의 해시 맵에 각각 번호를 추가해놓고, 돌면서 하나씩 가져갈까 생각을 했다. 근데 배열 크기가 엄청 커지면 시간이 초과될 것 같았다.
• 생각 2) nums 배열에 종류가 몇 개가 들어있는지에 따라 결국 흐름이 달라짐이 생각났다.
  • 종류 개수가 a라고 할때,
  • a ≥ n//2 이면, 가져갈 수 있는 종류의 개수는 n//2은 거뜬히 가져갈거고,
  • 반대로 a < n//2 이면, 가져갈 수 있는 종류의 개수는 a일 거다. 
  • => 생각 2를 구현하기로 했다. 

# 첫 시도 :: 실패 

• 해시맵으로 풀고 싶어서, hlist를 선언하고 각 번호를 n으로 나눈 나머지를 key값으로 하고, 그에 해당하는 nums[i]값을 value에 list형식으로 추가했다. 
• 그랬더니 번호끼리 잘 묶이긴 하는데 빈 리스트 []가 생겨, 얘를 제외하고 cnt를 셌다. 
• 생각해보니 cnt가 결국 nums 배열에 있던 종류의 개수여서 방법을 바꿨다. 

# 같은 종류 같은 번호 가짐 
# N마리 중 N/2마리 가져가기 
# 최대한 다양한 종류 (같은 번호를 가지면 패스)
# n개의 칸에 각각 추가해놓고 돌아가면서 하나씩 가져가자 
n = len(nums) # 여기서 2/n개만 가져가는 거잖아
hlist = [[] for _ in range(n)] 
#hlist = dict.fromkeys([x for x in range(n)], [])
#print(hlist)
for i in range(n):
    h_n = nums[i] % n 
    hlist[h_n].append(nums[i])
# h_list를 돌면서 []가 아닌 게 몇개인지 세고 그게 2/n개보다 크면 답은 2/n 작으면 아닌 개수가 답 
print(hlist)
cnt = 0 
for sl in hlist:
    if sl != []: cnt += 1
if cnt >= (n//2): return n//2
else: return cnt

 

📌 풀이 코드 

=> nums 배열 내 중복을 제거하면, 종류의 개수를 알 수 있다. 

=> 이걸로 생각2)에 기반해 아래와 코드를 짜면 정답이다.

 

# 11시 시작 
def solution(nums):
    answer = 0
    # 배열 안에 서로 다른 종류가 몇 개 있는지 봐 
    # 그게 n//2보다 크면, 답은 n//2 
    # 그게 n//2보다 작으면, 답은 그거 
    n = len(nums) # 총 몇 마리인지 일단 알아두고
    nums = set(nums) # 중복 숫자들 제거하고 
    if len(nums) >= (n//2): 
        return n//2
    else: 
        return len(nums)