Notion에서 작성된 글이라, 여기 에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Beginner] 폰켓몬

[폰켓몬]

2기 1일차에 풀었던 문제로, 해시 + Greedy 문제이다.

• 최대한 다양한 종류의 폰켓몬을 가진다 = 중복 없이 최대한 많은 폰켓몬을 선택한다.
  • 이를 위해 set()을 이용한다.
• 최대 $N/2$마리를 가져갈 수 있으므로, 폰켓몬의 종류가 $N/2$보다 많더라도 $N/2$마리만 가져갈 수 있으며, 폰켓몬의 종류가 $N/2$보다 적다면 종류의 수만큼을 가져가는 것이 최대한 다양한 종류의 폰켓몬을 가지는 방법이다.

Solution. $O(n)$

def solution(nums):
    return min(len(nums)//2, len(set(nums)))

---

[Middler] 의상

[의상]

BOJ 9375. 패션왕 신해빈 과 동일한 해시 + 조합 문제이다.

• 동일한 종류의 의상을 묶어서, 각 종류의 의상이 몇 가지가 존재하는지 센다.
• 각 의상의 종류별 개수를 $A_i$라고 하자. 답은 아래와 같다.

• TC #1 을 같이 생각해 보자.
  • headgear에는 yellow_hat, green_turban이 있고, eyewear에는 blue_sunglasses가 있다.
  • 각 종류별로 최대 1가지 의상만 착용할 수 있으므로, headgear는

    1. headgear를 착용하지 않는 방법

    2. yellow_hat만 착용하는 방법

    3. green_turban만 착용하는 방법

       의 3가지 방법이 있다.

  • headgear를 착용하는 각 방법에 대해 eyewear는

    1. eyewear를 착용하지 않는 방법

    2. blue_sunglasses만 착용하는 방법

       의 2가지 방법이 있다.

  • 여기에서, 하루에 최소 한 개의 의상은 입는다고 했으므로, 모두 착용하지 않는 경우를 빼주면 된다. ∴ $3 \times 2 - 1 = 5$

• 다 벗고 모자만 쓰고 다니기도 하나보다…

Solution 1. $O(n)$

def solution(clothes):
    c_dict = dict()
    for c in clothes:
        if c[1] in c_dict:
            c_dict[c[1]].append(c[0])
        else:
            c_dict[c[1]] = [c[0]]
    
    answer = 1
    for type in c_dict.keys():
        answer *= (len(c_dict[type])+1)
    
    return answer-1

Solution 1-2. $O(n)$

def solution(clothes):
    c_dict = dict()
    for c in clothes:
        if c[1] in c_dict:
            c_dict[c[1]] += 1
        else:
            c_dict[c[1]] = 1
    
    answer = 1
    for type in c_dict.values():
        answer *= (type+1)
    
    return answer-1

• 부랴부랴 문제를 다 풀고 다시 보니, 굳이 각 의상의 이름을 append하고 len을 구할 필요가 없었다. 단순히 개수만 세어줌으로써 코드가 간결해졌고, 메모리 사용량 또한 줄어들었다.

Solution 1-3. defaultdict + reduce $O(n)$

from collections import defaultdict
from functools import reduce

def solution(clothes):
    c_dict = defaultdict(int)
    
    for c in clothes:
        c_dict[c[1]] += 1
    
    return reduce(lambda x, y: x*(y+1), c_dict.values(), 1)-1

• defaultdict와 reduce를 이용하면 아주 깔끔하게 풀 수 있다.
• 심지어 defaultdict는 이러한 상황에서 기존의 dictionary보다 더 빠르게 동작하므로 꼭 알아두어야 겠다.

★ 새롭게 알게된 것

defaultdict

• dictionary를 이용하는 많은 문제들에서 아래와 같은 꼴로 ‘등록’ 해주는 느낌의 코드를 정말 많이 작성했었다. 해당 key가 존재하지 않는다면 1로 초기화시켜주고, 이미 존재한다면 1을 증가시켜주는 식이다.

  dictionary = {}
  for e in a:
  	if e in dictionary:
  		dictionary[e] += 1
  	else:
  		dictionary[e] = 1

  • 왜 이렇게 했는가? 를 생각해 보면, key를 통해 접근하여 value를 변경할 때 해당 key가 dictionary에 없으면 KeyError가 발생하기 때문이다.

• 이를 아주 깔끔하게 만들어주는 자료구조가 있는데, 바로 defaultdict 이다.

  from collections import defaultdict
  
  dictionary = defaultdict(int)
  
  for e in a:
  	dictionary[e] += 1

  사용 방법

  • from collections import defaultdict
  • 기본값을 설정하는 함수(e.g., int, list, …)를 인자로 전달한다.

  장점

  1. 코드가 간결해진다.

  2. key의 존재 여부를 확인하는 작업이 줄어들기 때문에 dictionary에 비해 더 빠르다.

     • Test Code

       data = [i % 1000 for i in range(10000000)]
       
       # dict
       start_time = time.time()
       count_dict = {}
       for n in data:
           if n in count_dict:
               count_dict[n] += 1
           else:
               count_dict[n] = 1
       dict_time = time.time() - start_time
       print(f"기존 dict: {dict_time:.6f}초")
       
       # defaultdict
       start_time = time.time()
       count_defaultdict = defaultdict(int)
       for n in data:
           count_defaultdict[n] += 1
       defaultdict_time = time.time() - start_time
       print(f"defaultdict: {defaultdict_time:.6f}초")
       
       # result
       print(f"defaultdict가 기존 dict보다 {dict_time / defaultdict_time:.2f}배 더 빠릅니다.")

       • Result

         기존 dict: 1.053779초
         defaultdict: 0.782480초
         defaultdict가 기존 dict보다 1.35배 더 빠릅니다.
         기존 dict: 1.061414초
         defaultdict: 0.821016초
         defaultdict가 기존 dict보다 1.29배 더 빠릅니다.
         기존 dict: 1.023519초
         defaultdict: 0.819530초
         defaultdict가 기존 dict보다 1.25배 더 빠릅니다.
         기존 dict: 1.056884초
         defaultdict: 0.772668초
         defaultdict가 기존 dict보다 1.37배 더 빠릅니다.
         기존 dict: 1.021496초
         defaultdict: 0.834369초
         defaultdict가 기존 dict보다 1.22배 더 빠릅니다.

reduce

• sum() 처럼 iterable을 받아서 곱해준 결과를 반환해주는 방법이 없을까 하다가 알게 되었다.
• 전체적으로는 map() 과 유사하다. reduce(*function*, *iterable[, initializer]*) 의 형식을 사용하는데, map()과 다른 점은 주어진 iterable의 모든 항목에 대해 누적된 연산을 수행하여 단일 결과를 반환한다는 점이다.

---

[Challenger] 테이블 해시 함수

[테이블 해시 함수]

• 해시를 이용하여 푸는 문제가 아닌 해시 개념이 녹아든 단순 구현 문제이다.

• data 는 0-indexed임에 주의하며, 문제 설명에 따라 차근차근 구현해 나가면 쉽게 풀리는 문제이다.

Solution. $O(n \lg n) + O(nm)$

• $m$은 data의 원소의 길이를 의미한다.

def solution(data, col, row_begin, row_end):
    data.sort(key=lambda x: (x[col-1], -x[0]))

    answer = 0
    for i in range(row_begin-1, row_end):
        answer ^= sum(data[i][j] % (i+1) for j in range(len(data[i])))
    
    return answer

---