프로그래머스-폰켓몬

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

프로그래머스

나의 무지성 시간초과 풀이

아앗...

사실 보자마자 뭔가 Combinations 이용해서 할려고 했는데, 제한사항을 보지 않아서 시간초과 발생함. 따라서 해당 방법은 불가능

이중 포문이라 시간복잡도 말도 안되는 수치가 된 듯하다.

# n마리 중에서 n/2마리 가져가셈
# 종류에 따라 번호 부여 -> 같은 종류는 같은 번호
# EX) 4마리 -> [3, 1, 2, 3] -> 3번 2마리 + 1번 1마리 + 2번 1마리
# 4마리 중에서 2마리 고르는 케이스
# 1. (3[1번째], 1)
# 2. (3[1번째], 2)
# 3. (3[1번째], 3[4번쨰])
# 4. (1, 2)
# 5. (1, 3[4번째])
# 6. (2, 3[4번째])
# => 3번의 경우는 동일한 것으로 취급 따라서 2종류가 가장 많음

from itertools import combinations

def solution(nums):
    targetCount = len(nums) // 2
    answer = []
    for data in combinations(nums, targetCount):
        temp = []
        maxCount = 0
        for x in data:
            if x not in temp:
                maxCount += 1
            temp.append(x)
        answer.append(maxCount)
    
    
    return max(answer)

Set을 사용하면 깔끔

위에 코드 에러터지고 바로 Set을 사용하면 되지 않을까 생각하고, set을 사용했더니 통과(이게...? 돌아간다고??)

# n마리 중에서 n/2마리 가져가셈
# 종류에 따라 번호 부여 -> 같은 종류는 같은 번호
# EX) 4마리 -> [3, 1, 2, 3] -> 3번 2마리 + 1번 1마리 + 2번 1마리
# 4마리 중에서 2마리 고르는 케이스
# 1. (3[1번째], 1)
# 2. (3[1번째], 2)
# 3. (3[1번째], 3[4번쨰])
# 4. (1, 2)
# 5. (1, 3[4번째])
# 6. (2, 3[4번째])
# => 3번의 경우는 동일한 것으로 취급 따라서 2종류가 가장 많음

def solution(nums):
    targetCount = len(nums) // 2
    answer = set(nums)
    if len(answer) <= targetCount:
        return len(answer)
    else:
        return targetCount

 

dictionary를 사용한 방법(참고)

결국 코드를 전체적으로 보면 중복된 것을 지우고 카운팅하는 게 방법. 원래는 이 방법으로 생각을 해봤지만, 떠오르지 않아서 Combinations 사용하고 시간초과로 빠꾸 당하고 Set으로 해결(인생 같네)

def solution(nums):
    n_dict = dict()
    
    for n in nums:
        n_dict[n] = 1 # 중복이 되어도 1로 간주 
        
    if len(nums) // 2 <= len(n_dict): # 전체 종류의 수/2와 중복 제거된 종류의 수를 비교
        return len(nums) // 2 # 전체 종류의 수/2값이 작거나 같다면 즉시 반환
    
    return len(n_dict)