[Python] 프로그래머스 알고리즘 고득점 Kit ✅ 완전탐색 (~ing)

[Level 1] 최소 직사각형

def solution(sizes):
    answer = 0
    
    w_list = []
    h_list = []
    
    for size in sizes:
        # 큰 값들은 다 왼쪽으로 넘기기
        if size[0] < size[1]:
            tmp = size[0]
            size[0] = size[1]
            size[1] = tmp
        
        w_list.append(size[0])
        h_list.append(size[1])
    
    answer = max(w_list) * max(h_list)
    
    return answer

 

[Level 1] 모의고사

def solution(answers):
    answer = []
     
    # 수포자 답안 패턴
    person_1 = [1, 2, 3, 4, 5]
    person_2 = [2, 1, 2, 3, 2, 4, 2, 5]
    person_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    
    # 맞은 개수 count
    one_count = 0 ; two_count = 0 ; three_count = 0
    
    # 정답 개수
    answers_len = len(answers)
    
    num_1 = person_1 * ((answers_len // len(person_1)) + (answers_len % len(person_1)))
    num_2 = person_2 * ((answers_len // len(person_2)) + (answers_len % len(person_2)))
    num_3 = person_3 * ((answers_len // len(person_3)) + (answers_len % len(person_3)))
    
    # 정답 비교
    for i in range(answers_len):
        if num_1[i] == answers[i]: one_count += 1
        if num_2[i] == answers[i]: two_count += 1
        if num_3[i] == answers[i]: three_count += 1
    
    # 가장 많이 맞힌 사람 찾기
    max_count = max(one_count, two_count, three_count)
    if one_count == max_count: answer.append(1)
    if two_count == max_count: answer.append(2)
    if three_count == max_count: answer.append(3)
    
    return answer

 

[Level 2] 소수 찾기

• itertools는 파이썬에서 반복되는 데이터를 처리하는 기능을 하는 라이브러리
• permutations는 순열 / combinations는 조합에 관한 클래스 → 이번 문제 풀이에서는 이를 활용하고자 함
• (추가 메모) 소수 판별 시, 제곱근까지만 확인하기 - 안하면 시간 초과됨 ...

from itertools import permutations # 순열

def is_prime(n):
    '''소수 판별 함수'''
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1): # 제곱근까지만 확인 (이거 안하면 시간 초과됨)
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    
    # 순열을 활용해 모든 조합 찾기
    numbers_list = [int(i) for i in numbers]  # 각 하나의 숫자로 변환
    numbers_list_new = []
    
    for i in range(1, len(numbers_list)+1):
            new = list(permutations(numbers_list, i))
            
            for j in range(len(new)):
                numbers_list_new.append(new[j])
    
    # 가능한 조합의 수로 변환(join, map 활용)
    final_numbers = []  # [17, 1, 7, 71]
    
    for i in numbers_list_new:
        final_numbers.append(int(''.join(map(str, list(i)))))  # 정수로 변환 + 0도 추가로 제거 
        
    final_numbers = list(set(final_numbers)) # 중복 제거
    
    # 소수인지 확인 후 count
    for num in final_numbers:
        if is_prime(num): answer += 1

    return answer

 

[Level 2] 카펫

• 중앙은 노란색, 테두리 1줄은 갈색이라는 점에 Focus !!
• 이를 위해서 노란색으로 만들 수 있는 직사각형을 모두 만들고, 갈색 테두리로 다 감싸지는 지 확인해야 한다.

def solution(brown, yellow):
    answer = []
    total_carpets = brown + yellow
    
    # 약수 구하기 (1과 자기 자신 제외)
    number_list_yellow = [i for i in range(1, yellow + 1) if yellow % i == 0]
    
    # 조합을 찾아보자 (완전 탐색!)
    results_yellow = []
    for i in number_list_yellow:
        for j in number_list_yellow:
            if i * j == yellow and i >= j: # i >= j는 가로 길이가 세로보다 긴 것
                results_yellow.append([i, j])
    # print(results_yellow)
    
    # 찾은 조합 중에서 중앙은 노란색, 테두리 1줄은 갈색인 것
    for i, j in results_yellow:
        if (i+2) * (j+2) == total_carpets:
            answer.append(i+2)
            answer.append(j+2)
    
    return answer

 

[Level 2] 피로도

• 이번에도 순열(permutations)을 사용해봄. 완전 탐색에서 모든 경우의 수를 구해야 해서 거의 필수적인 것 같다.

from itertools import permutations

def solution(k, dungeons):
    answer = -1

    # 던전 탐험 모든 경우의 수 구하기 (순열 사용)
    for perm in permutations(dungeons):
        cnt, kk = 0, k # 하나의 경우의 수 실행마다 초기화
        for i, j in perm:
            if kk >= i:
                kk-= j
                cnt += 1
        answer = max(answer, cnt)
    
    return answer

 

[Level 2] 전력망을 둘로 나누기

ing

 

[Level 2] 모음사전

ing