HASH: Key-value쌍

counter

• collections 라이브러리
• list=> counter: key/ value:dictionary

완주하지 못한 선수

• 다른 리스트와 비교

import collections 

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

전화번호 목록

• 자기자신과 비교

def solution(phoneBook):
    phoneBook = sorted(phoneBook) # 정렬 필요

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

위장

• 서로 다른 리스트에서 모든 조합

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

• (headgear +1) * (eyewear +1) -1
  착용하지 않는 경우/모든 의상을 착용하지 않는 경우는 배제

• reduce(lambda x, y : x * (y+1), count.value(), 1) -1

3rd parameter: 1
2nd parameter: 의상의 수=> y
Counter({'headgear': 2, 'eyewear': 1}) =
1( (1 x (2+1) ) x (1+1) ) -1
=5

reduce 사용예시

• answer = reduce(lambda x, y : x + y, [2,4,6,8,10])
  ((((2 + 4) + 6) + 8) + 10)

정렬

K번째 수

• 2리스트 정보따라 value 추출하여 리스트에 담기

def solution(array, commands):
    return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))

• commands에 map,lambda 적용, i= x[0], j = x[1], k = x[2]

def solution(array, commands):
    return [sorted(array[i-1:j])[k-1] for i,j,k in commands]

map : for문도 불필요

set(map(lambda x: x ** 2, range(5)))
>>{0, 1, 4, 9, 16}

가장 큰 수

• 앞자리 기준 내림차순 정렬
• x*3을 통해서 전체 자릿수를 맞춰준 뒤 비교

def solution(num): 
    num = list(map(str, num)) 
    num.sort(key = lambda x : x*3, reverse = True)  # 자릿수 맞추기
    return str(int(''.join(num))) # input이 0,0,0 => 0으로 변환 

• '333', '303030', '343434', '555', '999' (str: 순서대로 숫자만 비교)
  sorted : '303'030 -> '333' -> '343'434 -> '555' -> '999'
  reverse=True
  ['9', '5', '34', '3', '30']

H-index

• x=y에 가장 가까운 값 찾으면 된다.
• [3, 0, 6, 1, 5]
  sorted : [6,5,3,1,0]
  (1, 6) -> 1
  (2, 5) -> 2
  (3, 3) -> 3
  (4, 1) -> 1
  (5, 0) -> 0
  [1, 2, 3, 1, 0]

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1))) # (index, value) 
    return answer 

def solution(citations):
    citations.sort()
    article_count = len(citations)

    for i in range(article_count):
        if citations[i] >= article_count-i:
            return article_count-i
    return 0

완전탐색

모의고사

def solution(answers):
  p = [[1,2,3,4,5],
      [2,1,2,3,2,4,2,5],
      [3,3,1,1,2,2,4,4,5,5]]
  s = [0] * 3

  for idx, a in enumerate(answers):
    for idx2, pattern in enumerate(p):
      if a==pattern[idx%len(pattern)]:
        s[idx2] += 1 
 
  return [i+1 for i in range(len(s)) if s[i] == max(s)]

• cycle library
• next

from itertools import cycle

def solution(answer):
  giveups = [
    cycle([1,2,3,4,5]),
    cycle([2,1,2,3,2,4,2,5]),
    cycle([3,3,1,1,2,2,4,4,5,5])
  ]
  scores=[0,0,0]
  
  for num in answer:
    for i in range(3):
      if next(giveups[i])==num:
        scores[i] += 1

  return [i+1 for i in range(len(scores)) if scores[i]==max(scores)]

소수찾기 : 에라토스테네스의 체

from itertools import permutations

def solution(numbers):
    answer = []                                   
    nums = [n for n in numbers]                   # numbers를 하나씩 자른 것
    per = []                                      
    for i in range(1, len(numbers)+1):            # numbers의 각 숫자들을 순열로 모든 경우 만들기
        per += list(permutations(nums, i))        # i개씩 순열조합
    new_nums = [int(("").join(p)) for p in per]   # 각 순열조합을 하나의 int형 숫자로 변환

    for n in new_nums:                            # 모든 int형 숫자에 대해 소수인지 판별
        if n < 2:                                 # 2보다 작은 1,0의 경우 소수 아님
            continue
        check = True            
        for i in range(2,int(n**0.5) + 1):        # n의 제곱근 보다 작은 숫자까지만 나눗셈
            if n % i == 0:                        # 하나라도 나눠떨어진다면 소수 아님!
                check = False
                break
        if check:
            answer.append(n)                      # 소수일경우 answer 배열에 추가

    return len(set(answer))                       # set을 통해 중복 제거 후 반환

from itertools import permutations

def prime_list(n):
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False 
    
    for i in range(2, int(n ** 0.5) + 1):
        if prime[i]:
            for j in range(i*i, len(prime), i):
                prime[j] = False
    return prime
    
def solution(numbers):
    numbers = list(numbers)
    number_set = set()
    
    for i in range(len(numbers)):
        number_set |= set(map(int, map(''.join, permutations(numbers, i+1))))
    
    prime = prime_list(max(number_set))
    
    answer = 0
    for number in number_set:
        if prime[number]:
            answer += 1
    return answer

** set을 사용하면 속도가 느리다

def solution(n):
    num = set(range(2, n+1))
    
    for i in range(2, n+1):
        if i in num:
            num -= set(range(2*i, n+1, i))
    return len(num)

카펫

def solution(brown, yellow):    
    total = brown + yellow
    for i in range(3, int(total**0.5) + 1):
        if not total % i and (i-2) * ((total//i)-2) == yellow:
            return [total//i, i]

def solution(brown, red):
    for i in range(1, int(red**(1/2))+1):
        if red % i == 0:
            if 2*(i + red//i) == brown-4:
                return [red//i+2, i+2]

깊이/너비우선탐색(DFS/BFS)

타겟넘버

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer

• 완전탐색

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque() #queue 생성
    
    length = len(numbers)
    queue.append([-numbers[0], 0])
    queue.append([+numbers[0], 0])
    
    while queue :
        num, i = queue.popleft()
        if i+1 == length :
            if num == target : answer += 1
        else :
            queue.append([num - numbers[i + 1], i + 1])
            queue.append([num + numbers[i + 1], i + 1])
    
    return answer

def solution(numbers, target):
    super = [0]
    for i in numbers:
        sub=[]
        for j in super:
            sub.append(j+i)
            sub.append(j-i)
        super=sub
    return super.count(target)

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

스택큐

주식가격

def solution(prices):
    length = len(prices)
    answer = [ i for i in range (length - 1, -1, -1)]
    
    stack = [0]
    for i in range (1, length, 1):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

다리를 지나는 트럭

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0

    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()

        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck

        answer += 1

    answer += bridge_length

    return answer

프린터

def solution(priorities, location):
    answer = 0
    from collections import deque

    d = deque([(v,i) for i,v in enumerate(priorities)])

    while len(d):
        item = d.popleft()
        if d and max(d)[0] > item[0]:
            d.append(item)
        else:
            answer += 1
            if item[1] == location:
                break
    return answer

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

기능개발

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

from math import ceil

def solution(progresses, speeds):
    daysLeft = list(map(lambda x: (ceil((100 - progresses[x]) / speeds[x])), range(len(progresses))))
    count = 1
    retList = []

    for i in range(len(daysLeft)):
        try:
            if daysLeft[i] < daysLeft[i + 1]:
                retList.append(count)
                count = 1
            else:
                daysLeft[i + 1] = daysLeft[i]
                count += 1
        except IndexError:
            retList.append(count)

    return retList

힙

더맵게

import heapq
   
def solution(scoville, k):
    heap = []
    for num in scoville:
         heapq.heappush(heap, num)
    mix_cnt = 0
    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        mix_cnt += 1
    return mix_cnt

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  

    return answer

from heapq import heapify, heappush, heappop
def solution(scoville, K):
    heapify(scoville)
    for i in range(1000000):
        try:
            heappush(scoville, heappop(scoville)+(heappop(scoville)*2))
            if scoville[0] >= K: return i+1
        except:
            return -1