[3주차 탐색] 코드 리뷰

탐색

1. Lv1 - 세 소수의 합

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))

    num = list(num)
    answer = 0

    for i in range(len(num)):
        for j in range(i + 1, len(num)):
            if (n - num[i] - num[j]) in num[j + 1:]:
                answer += 1

    return answer

• 에라토스테네스의 체 : 시간복잡도는 O(NloglogN), N = 입력으로 주어진 n
• 소수 구하기 : 시간복잡도는 O(M**3), M = 소수의 개수
• num 대신 prime_numbers, primes와 같이 명확한 이름을 붙이기

 

2. Lv2 - 카펫

def solution(brown, red):
    total = brown + red

    for height in range(3, total):
        width = total // height
        if total % height != 0 and width <= height:
            continue
        if (height - 2) * (width - 2) == red:
            return [width, height]

• 시간복잡도 = O(N), N = 전체 격자 수

 

3. Lv2 - 주사위 게임

def solution(monster, S1, S2, S3):
    monster = [i - 1 for i in monster]

    answer = 0
    for i in range(1, S1 + 1):
        for j in range(1, S2 + 1):
            for k in range(1, S3 + 1):
                if i + j + k not in monster:
                    answer += 1

    return int(answer / (S1 * S2 * S3) * 1000)

• 시간복잡도 = O(N**3)

 

4. Lv3 - 예산

def solution(budgets, M):
    budgets.sort()
    answer = budgets[-1]  

    if sum(budgets) < M:
        return answer
    else:
        while sum(budgets) > M:
            answer = answer - 1
            smaller = sum([budget for budget in budgets if budget < answer])
            answer_sum = answer * len([budget for budget in budgets if budget >= answer])
            temp_sum = smaller + answer_sum
            if temp_sum <= M:
                return answer

    return answer

• 시간이 오래 걸리는 완전 탐색으로 풀었음 > 이진 탐색을 구현하여 풀어볼 것
• temp_sum은 `temp_sum = sum(min(budget, answer) for budget in budgets)`으로 줄일 수 있음
• `while sum(budgets) > M` -> `while True:`
• early return 다음에는 else문을 쓰지 않아도 됨

 

5. Lv3.5 - 게임 맵 최단거리

from collections import deque

def visitable(n, m, x, y, maps):
    return 0 <= x < n and 0 <= y < m and maps[x][y] == 1

def solution(maps):
    answer = 2
    n = len(maps)
    m = len(maps[0])
    queue = deque()
    queue.append((0, 0))
    maps[0][0] = 0
    DELTAS = ((0, 1), (0, -1), (1, 0), (-1, 0))  # R, L, D, U

    while queue:
        same_depth_queue, queue = queue, []

        for x, y in same_depth_queue:
            for dx, dy in DELTAS:
                next_x, next_y = x + dx, y + dy
                if next_x == n-1 and next_y == m-1:
                    return answer
                elif visitable(n, m, next_x, next_y, maps):
                    # print(next_x, next_y, answer)
                    queue.append((next_x, next_y))
                    maps[next_x][next_y] = 0
        answer += 1
    return -1

 

6. Lv4 - 버스 여행

import numpy as np

def solution(n, signs):
    answer = signs
    cnt = 0
    while cnt <= n:
        arr_multi = np.dot(signs, signs)
        for i in range(n):
            for j in range(n):
                if arr_multi[i][j]:
                    answer[i][j] = 1
        if (arr_multi == answer).all():
            break
        cnt += 1

    return answer

• 행렬곱의 시간복잡도는 O(NlogN ~ N**2)이며, 최대 n번 반복하므로 전체 복잡도는 O(N**2logN ~ N**3)
• 다른 접근법도 생각해보기

 

모의고사 - 리뷰 후 수정하기

1. 소수 만들기

from itertools import combinations

def solution(nums):
    prime_set = list(combinations(nums, 3))
    sum_list = list(map(sum, prime_set))
    answer = len(sum_list)

    for sum_value in sum_list:
        for number in range(2, sum_value // 2):
            if sum_value % number == 0:
                answer -= 1
                break
    return answer

 

2. 가로등 - 못 풀었음😂