https://school.programmers.co.kr/learn/courses/30/lessons/1845
처음에는 조합을 사용해 직접 nums 배열 속의 포켓몬 번호를 조합하여, 중복되지 않은 포켓몬의 개수를 셌다. 이후 가장 큰 값을 골라 출력했다.
해당 방법은 시간 초과 문제를 나타냈다. 생각해보니 nums에 들어있는 포켓몬의 수가 매우 많을 경우, 가능한 모든 조합을 해보고 개수를 세고, 그 숫자 중 가장 큰 값을 고르는 과정에서 시간 복잡도가 증가했을 것이다.
다양한 풀이법을 검색하던 중, 직접 조합하지 않고도 개수를 알 수 있는 방법을 발견하였다. 알고리즘은 다음과 같다.
뽑을 캐릭터의 수(N/2)와 nums 배열 안 중복되지 않는 캐릭터의 수를 비교한다. 뽑을 캐릭터의 수(pick)가 중복되는 캐릭터의 수(count)보다 작은 경우, 정답은 뽑을 캐릭터의 숫자(pick)이다. 뽑을 캐릭터의 수(pick)가 중복되지 않는 캐릭터의 수(count)보다 큰 경우, 정답은 중복되지 않는 캐릭터의 수(count)이다.
- pick < count : answer = pick
- pick > count : answer = count
예시를 통해 설명하겠다.
1) nums : [3, 1, 2, 3]
2) nums : [3, 3, 3, 2, 2, 4]
3) nums : [3, 3, 3, 2, 2, 2]
# 시간 초과 문제를 해결함
# 처음에는 순열(combination)을 통해 직접 뽑고, 뽑은 값의 중복을 제거해 개수를 세서 가장 개수가 많은 것을 출력함
# => 다른 방법을 찾아보면서 직접 뽑고 추릴 필요가 없음을 깨닫고 아래 방법으로 진행
def solution(nums):
pick = len(nums)//2 # 뽑아야 하는 캐릭터의 개수
count = len(set(nums)) # nums에 저장된 캐릭터 숫자의 중복을 제거한 후 개수 (중복을 제거한 캐릭터 개수)
if pick < count: # 뽑을 캐릭터 개수가 전체 캐릭터 개수(중복 x)보다 작은 경우
answer = pick # 뽑을 캐릭터 수가 정답이다
else:
answer = count # 뽑을 캐릭터 개수가 전체 캐릭터 개수(중복 x)보다 큰 경우, 전체 캐릭터 개수가 정답
return answer
def solution(nums):
answer = 0
kind = len(set(nums))
if kind > len(nums)/2:
answer = len(nums)/2
else:
answer = kind
return answer
1), 2)번 방법 모두 조합을 통해 모든 가능성을 직접 구하는 연산을 진행하였기 때문에 시간 복잡도가 매우 높다.
from itertools import combinations
# 1) 리스트 중복 요소 제거 : for문(반복문) 사용하기
def solution(nums):
comb = list(combinations(nums, len(nums)//2))
lens = []
for arr in comb:
alist = []
for i in range(len(arr)):
if arr[i] not in alist:
alist.append(arr[i])
lens.append(len(alist))
answer = max(lens)
return answer
# 2) 리스트 중복 요소 제거 : set 연산 사용하기
from itertools import combinations
def solution(nums):
comb = list(combinations(nums, len(nums)//2))
lens = []
for arr in comb:
alist = list(set(arr))
lens.append(len(alist))
answer = max(lens)
return answer
✏️ 생각하지 못한 방법으로 시간을 빠르게 단축할 수 있었다. 앞으로도 많은 문제를 풀어보면서 문제에 접근할 수 있는 다양한 방법들을 빠르게 생각하는 연습을 해야 겠다.