[10회차]

Programmers Level.2 큰 수 만들기

def find_larger(number):
    a = 0
    b = 0
    while b < len(number):
        b += 1
        if b == len(number):
            return b
        if number[b] == number[a] and b == a + 1:
            a += 1
        elif number[b] >= number[a]:
            return b


def solution(number, k):  # 첫째 자리 수와 그 보다 이상인 값 중 첫 번째로 나오는 값을 찾는다.
    number = list(map(int, number))  # 그 사이에서 최솟값을 차례로 지우자.
    while k > 0:  # 지울 게 없다면 첫째 자리수를 지우고, 이 과정을 반복
        position = find_larger(number)
        mins = number.index(min(number[0:position]))
        number.pop(mins)
        k -= 1
    answer = ''
    for i in number:
        answer += str(i)
    return answer

-  내 아이디어는 첫째 자리 수와 다음에 나오는 그 보다 크거나 같은 값 사이에서 값을 하나씩 제거하는 방법이다. 사이에 있는 값 중 최솟값부터 제거하고 제거할게 없으면 첫째 자리 수를 제거한 뒤, 위 과정을 반복한다. 즉, 새롭게 생기는 첫째자리 수와 그 다음에 나오는 크거나 같은 수를 잡고 그 사이의 숫자를 제거하는 과정을 반복. 이렇게 하면 될 줄 알았는데 안되더라. 아이디어가 떠오르지 않아 구글 검색을 통해 해결. (일명 컨닝..)

def solution(number, k):
    answer = []
    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)

 - 앞에서 부터 한자리씩 넣으면서 앞자리부터 최댓값을 완성한다는게 아이디어.

 

 

Programmers Level.2 피로도

from itertools import permutations


def cnt_dungeons(k, dungeon_case):
    result = 0
    for dungeon in dungeon_case:
        if k < dungeon[0]:
            return result
        k -= dungeon[1]
        result += 1
    return result


def solution(k, dungeons):
    answer = 0
    for dungeon_case in permutations(dungeons, len(dungeons)):
        if answer < cnt_dungeons(k, dungeon_case):
            answer = cnt_dungeons(k, dungeon_case)
    return answer

 - 아무리 고민해도 생각이 나질 않아서 모든 경우의 수를 탐색해서 풀긴 했는데 이게 맞는 걸까? 언제는 모든 경우를 고려하면 답이 틀리고 언제는 해도 되고... 어렵다. 이 문제의 경우 던전의 수를 8개 제한으로 줬기 때문에 모든 경우를 탐색해도 되긴 했던 듯. 

 

 

Programmers Level.2 배달

import heapq

def solution(N, road, K):
    INF = 500001
    distance = [INF] * (N + 1)
    graph = [[] for _ in range(N + 1)]
    for a, b, c in road:
        graph[a].append((b,c))
        graph[b].append((a,c))
    q = []
    heapq.heappush(q, (0, 1))
    distance[1] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    answer = 0
    for i in distance:
        if i <= K:
            answer += 1
    return answer