[탐욕법] 모음_코딩테스트 고득점 Kit

체육복

링크텍스트

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

def solution(n, lost, reserve):
	s = set(lost) & set(reserve) # set을 사용
    l = set(lost) - s
    r = set(reserve) - s
    for x in sorted(r):
    	if x - l in l:
        	l.remove(x - 1)
        elif x + 1 in l:
        	l.remove(x + 1)
    return n - len(l) 

조이스틱

링크텍스트

def solution(name):
    answer = 0
    min_left_right = len(name) # 왼쪽에서 오른쪽으로만 이동할 때 좌,우 조작 횟수
    next_idx = 0
    for idx, char in enumerate(name):
        # 위, 아래 조작 횟수의 최솟값 구하기
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        
        # 좌, 우 조작 횟수의 최솟값 구하기
        next_idx = idx + 1
        while next_idx < len(name) and name[next_idx] == 'A':
            next_idx += 1 # 현재 위치 이후 연속된 A 다음의 문자를 가리킴
        
        # 한 방향으로만 이동하는 경우와, 오른쪽으로 이동했다가 왼쪽으로 이동하는 경우를 비교
        min_left_right = min(min_left_right, idx + idx + len(name) - next_idx)
    answer += min_left_right
    return answer

큰 수 만들기

링크텍스트

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

def solution(number, k):
    answer = [] # Stack
        
    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
        
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

섬 연결하기

링크텍스트

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x: x[2]) 
    link = set([costs[0][0]])

    # Kruskal 알고리즘으로 최소 비용 구하기
    while len(link) != n:
        for v in costs:
            if v[0] in link and v[1] in link:
                continue
            if v[0] in link or v[1] in link:
                link.update([v[0], v[1]])
                answer += v[2]
                break
                
    return answer

def solution(n, costs):
    costs = sorted(costs, key=lambda x:x[2])
    node = set([costs[0][0], costs[0][1]])
    answer = costs[0][2]

    while len(node) != n:
        for i in range(1, len(costs)):
            if costs[i][0] in node and costs[i][1] in node:
                continue
            if costs[i][0] in node or costs[i][1] in node:
                node.update([costs[i][0], costs[i][1]])
                answer += costs[i][2]
                break
    return answer

단속카메라

링크텍스트

def solution(routes):
    # 1. route[1] 기준으로 정렬
    routes = sorted(routes, key=lambda route: route[1])
    # 2. -30000부터 카메라 위치를 찾습니다.
    prev_camera = -30000
    answer = 0

    # 3. routes를 순회합니다.
    for route in routes:
        # 1. 만약 최근 카메라가 route[0]보다 작은지 체크합니다.
        # 1-1. 작다면, 카메라를 한 개 더 세웁니다.
        # 1-2. 최근 카메라의 위치를 갱신합니다.
        if prev_camera < route[0]:
            answer += 1
            prev_camera = route[1]

    # 4. 카메라 개수를 반환합니다.
    return answer

def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1]) # routes를 차량이 나간 지점 (진출) 기준으로 정렬
    camera = -30001 # -30001부터 카메라 위치를 찾습니다.

    for route in routes:
        if camera < route[0]:
            answer += 1
            camera = route[1]
    return answer