[데브코스] TIL 4일차

해시
- 키(key)를 해시 함수(hash function)를 통해 해시 테이블에(hash table)의 각각 고유한 값(value)을 가리킴

- 다른 키가 같은 값을 가리킬 수 있음. 이것을 충돌(collision)이라 함

- 충돌을 회피하는 기법들이 있음

 

• 예제 - 완주하지 못한 선수

## 직접 구현
def solution(participant, completion):
    d = {}
    for x in participant: # 배열의 길이에 비례
        d[x] d.get(x,0) + 1
    for x in completion: # 배열의 길이에 비례
        d[x] -= 1
    dnf = [k for k,v in d.items() if v > 0] # 배열의 길이에 비례
    answer = dnf[0]
    return answer


## collections.Counter를 통해 풀어봄
from collections import Counter
def solution(participant, completion):
    participant = Counter(participant)
    for com in completion:
        participant[com] -= 1
        if participant[com] == 0:
            participant.pop(com)
    
    answer = participant.most_common(1)[0][0]
    return answer

 

 

탐욕법(Greedy)

- 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택함
- 탐욕법으로 최적해를 찾을 수 있는 문제 = 현재 선택이 해답의 최적성을 해치지 않을 때

- 지금 좋은게 끝에도 좋다. 게걸스럽궤

 

• 예제 1 - 체육복
  1) 탐욕법 적용 가능성 확인
  point. 예외가 생길 수 없을까?
  point. 빌려줄 학생들을 "정해진 순서"로 살펴야 하고, 이 "정해진 순서"에 따라 우선해 빌려줄 방향을 정함
  
  2) 적용 가능성 확인 됐으면 해결 방법을 생각함
  방법 1) 학생 수만큼 배열을 확보하고, 여기에 각자 가지고 있는 체육복 수를 기록함. 번호 순서대로 "스캔"하면서 빌려줄 관계를 정함
  방법 2) 만약 전체 학생 수가 매우 크다면? 그런데 여벌의 체육복을 가져온 학생은 매우 적다면?. 이때는 여벌의 체육복을 가져온 학생들의 번호를 정렬하고 이를 하나하나 보면서 빌려줄 수 있는 다른 학생을 찾아 처리한다

# 방법 1. 
def solution(n, lost, reserve):
    u = [1] * (n+2)
    for i in reserve: # reserve 길이에 비례
        u[i] += 1
    
    for i in lost: # lost 길이에 비례
        u[i] -= 1
    
    for i in range(1,n+1): # 전체 학생 수 (n)에 비례
        if u[i-1] == 0 and u[i] == 2:
            u[i-1:i+1] = [1,1]
        elif u[i] == 2 and u[i+1] == 0:
            u[i:i+2] = [1,1]
            
    return len([x for x in u[1:-1] if x > 0])


# 방법 2. 
def solution(n, lost, reserve):
    s = set(lost) & set(reserve) # 여분을 가져와 빌릴 필요가 없는 학생들
    l = set(lost) - s # 빌려야 하는 학생들
    r = set(reserve) - s # 빌려줄 수 있는 학생들
    
    for x in sorted(r): # 정렬하니 O(klogk)
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)
    
    return n - len(l)

 

• 예제 2 - 큰 수 만들기
  1) 원칙 살펴보기
  - 앞 자리에 큰 수가 오는게 전체를 크게 만들겠지?
  2) 예제 살펴보기
  
  3) 구현 단계
  - 주어진 숫자로부터 하나씩 꺼내어 모으되, 이미 모은 것 중 지금보다 작은 것은 빼냄(스택이 생각나네..)
  - 이렇게 모은 숫자들을 자릿수 맞추어 반환함

def solution(number, k):
    collected = []
    for idx, num in enumerate(number):
        while collected and collected[-1] < num and k:
            collected.pop()
            k -= 1
        if not k:
            collected += list(number[idx:])
            break
        collected.append(num)
    
    if k:
        return ''.join(map(str,collected[:-k]))
    else:
        return ''.join(map(str,collected))

 

 

 

 

정렬(Sort)

• 예제 - 가장 큰 수
  1) 해결 방법 : 빈 문자열로 수를 초기화. 가장 크게 만들 수 있는 수를 고름. 그 수를 현재 수에 이어 붙이고, 모든 수를 다 사용할 때까지 반복함
  2) (조금 나은) 해결 방법 : 빈 문자열로 수를 초기화. 수의 목록을 (크게 만드는것 우선으로) 정렬. 그 수를 현재 수에 이어 붙이고, 모든 수를 다 사용할 때까지 반복함
  3) 그렇다면 "크게 만드는 수"의 기준은? 길이가 다른데 앞자리 수가 같은 경우 조정 필요
  
  4) 구현 단계
  - 대소 관계 비교를 위한 기준 마련
  - 이것을 이용해 주어진 배열 정렬
  - 정렬된 배열을 이용해 문자열 표현을 완성

def solution(numbers):
    numbers = [str(x) for x in numbers] # 배열의 길이만큼
    numbers.sort(key=lambda x:(x*4)[:4], reverse=True) # O(nlogn)
    if numbers[0] == '0':
        answer = '0'
    else:
        answer = ''.join(numbers)
    return answer