[프로그래머스] 고득점 kit - 완전탐색 (Python/파이썬)

<문제링크>

https://school.programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

 

<풀이 전략>

1. 완전탐색이라 특별한 풀이전략보다 문제를 잘 읽고 충실히 구현하면 어렵지 않게 풀 수 있었던 문제들이다.

2. 6번째 문제인 전력망 둘로 나누기는 연결관계 파악을 위해 bfs로 풀었다. 

 

<정답 코드>

# 1. 최소 직사각형

def solution(sizes):
    
    sizes = list(map(sorted, sizes))
    x = max(sizes, key = lambda x: x[0])
    y = max(sizes, key = lambda x: x[1])
    
    answer = x[0] * y[1]

    return answer

 

# 2. 모의고사

def solution(answers):
    answer = []
    
    supo_1 = [1, 2, 3, 4, 5] * 2000
    supo_2 = [2, 1, 2, 3, 2, 4, 2, 5] * 1250
    supo_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * 1000
    
    cnt_1, cnt_2, cnt_3 = 0, 0, 0
    
    for i in range(len(answers)):
        ans = answers[i]
        
        if ans == supo_1[i]:
            cnt_1 += 1
        
        if ans == supo_2[i]:
            cnt_2 += 1
            
        if ans == supo_3[i]:
            cnt_3 += 1
        
    max_score = max([cnt_1, cnt_2, cnt_3])
        
    temp_list =  list(enumerate([cnt_1, cnt_2, cnt_3], start = 1))
                      
    for (idx, score) in temp_list:
        if score == max_score:
            answer.append(idx)
    
    return answer

 

# 3. 소수찾기

from itertools import permutations
import math

def solution(numbers):
    answer = 0
    
    def sieve(num):
        
        if num == 1:
            return False
        
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
            
        return True
    
    checked = set()
    
    for i in range(1, len(numbers) + 1):
        for perm in permutations(numbers, i):
                        
            num = ''.join(perm)
            num = int(num)
            
            if num == 0:
                continue
            
            if num in checked:
                continue
            
            checked.add(num)
            
            if sieve(num):
                answer += 1
            
        
        
    return answer

 

# 4. 카펫

def solution(brown, yellow):
    
    # 사각형 둘레의 절반
    perimeter_half = (brown +4) // 2
    
    # 사각형 가로 세로 길이 경우의 수 완전탐색
    for i in range(3, perimeter_half//2 + 1):
        
        j = perimeter_half - i
        
        if (i - 2) * (j - 2) == yellow:
            
            answer =  [j, i]
            break
    
    
    return answer

 

# 5. 피로도

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    N = len(dungeons)
    
    for perm in permutations(dungeons):
        cnt = 0
        left = k
        
        for i in range(N):
            
            energy = perm[i]
            if left >= energy[0]:
                left -= energy[1]
                cnt += 1
                
        answer = max(cnt, answer)
    
    return answer

 

# 6. 전력망 둘로 나누기

from collections import deque
from sys import maxsize


def bfs(start: int, graph: list, visited: list):

    queue = deque()
    queue.append(start)
    visited[start] = 1

    while queue:
        current = queue.popleft()

        for next in graph[current]:

            if visited[next]:
                continue

            visited[next] = 1
            queue.append(next)
    
    return sum(visited)


def solution(n:int, wires:list):
    answer = maxsize

    for i in range(len(wires)):

        cut_wire = wires[:]
        cut_wire.remove(wires[i])

        graph = [[] for _ in range(n + 1)]
        
        for node1, node2 in cut_wire:
            graph[node1].append(node2)
            graph[node2].append(node1)
        
        visited = [0 for _ in range(n + 1)]
        
        cnt = 0
        for edge in graph:
            if edge:
                cnt = bfs(edge[0], graph, visited)
                break

        diff = abs(n - cnt - cnt)

        
        answer = min(answer, diff)


    return answer

 

# 7. 모음사전

from itertools import product


def solution(word):
    vowel = ['A', 'E', 'I', 'O', 'U']
    word_list = []

    for length in range(1, 6):
        for prod in product(vowel, repeat=length):
            word_list.append(''.join(prod))

    word_list.sort()

    for i in range(len(word_list)):
        if word == word_list[i]:
            return i + 1