[1주차 - Day3] 파이썬을 무기로 코딩테스트 광탈을 면하자! (1)

해시(Hash) 대표 문제 풀이: 완주하지 못한 선수

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

탐욕법(Greedy) 대표 문제 풀이: 체육복

def solution(n, lost, reserve):
    u = [1] * (n + 2)
    for i in reserve:
        u[i] += 1
    for i in lost:
        u[i] -= 1
    for i in range(1, n + 1):
        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])

정렬(Sort) 대표 문제 풀이: 가장 큰 수

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x: (x * 4)[:4], reverse=True)
    if numbers[0] == '0':
        answer = '0'
    else:
        answer = ''.join(numbers)
    return answer

탐욕법(Greedy) 대표 문제 풀이: 큰 수 만들기

def solution(number, k):
    collected = []
    for i, num in enumerate(number):
        while len(collected) > 0 and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1
        if k == 0:
            collected += list(number[i:])
            break
        collected.append(num)
    
    collected = collected[:-k] if k > 0 else collected
    answer = ''.join(collected)
    return answer