프로그래머스 Study 3주차

소수 찾기 - 완전탐색, Level2

from math import sqrt
from itertools import permutations

'''
소수 판별 함수
@params: number (숫자)
@return: boolean (소수 여부)
'''
def is_prime_num(number):
    if number == 0 or number == 1:
        return False
    for i in range(2, int(sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True
    

def solution(numbers):
    
    answer = 0
    nums_with_comb = []
    
    for i in range(1, len(numbers) + 1): # 순열을 통해 가능한 모든 경우의 숫자를 얻음
        nums_with_comb += list(map(int, (map(''.join, permutations(numbers, i)))))
    nums_with_comb = set(nums_with_comb)
    
    for num_with_comb in nums_with_comb:
        if is_prime_num(num_with_comb):
            answer += 1
    return answer

1. itertools의 permutations(순열)를 통해 가능한 모든 경우의 숫자를 저장한다.

2. 모든 경우의 숫자들의 중복을 제거한다.

3. 소수 판별 함수를 통해 모든 경우의 숫자들이 소수인지 파악한다.

 

카펫 - 완전탐색, Level2

from math import sqrt

def solution(brown, yellow):

    yellows, browns = [], []
    
    for i in range(1, int(sqrt(yellow)) + 1):
        if yellow % i == 0:
            yellows.append([yellow // i, i]) # 가능한 노란 카펫의 [가로길이, 세로길이]
            
    for i in range(1, int(sqrt(yellow + brown)) + 1):
        if (yellow + brown) % i == 0:
            browns.append([(yellow + brown) // i, i]) # 가능한 갈색 카펫의 [가로길이, 세로길이]
    
    for yellow_x, yellow_y in yellows:
        for brown_x, brown_y in browns:
            if yellow_x + 2 <= brown_x and yellow_y + 2 <= brown_y:
                return [brown_x, brown_y]

1. 가능한 모든 노란 카펫과 갈색 카펫의 [가로길이, 세로길이]를 저장한다.

    1.1) 가로길이가 세로길이보다 크거나 같도록 저장한다.

2. 갈색 카펫의 가로길이, 세로길이가 노란 카펫의 가로길이, 세로길이보다 각각 최소한 2 이상 커야함을 이용해 정답을 구한다.

 

피로도 - 완전탐색, Level2

from itertools import permutations

'''
던전 탐험 함수
@params: k (현재 피로도), dungeons (순서가 정해져 있는 던전 리스트)
@return: number (통과한 던전 개수)
'''
def gaming(k, dungeons):
    
    result = 0
    
    for min_condition, consum in dungeons:
        if min_condition > k:
            return result
        else:
            k -= consum
            result += 1
    
    return len(dungeons)


def solution(k, dungeons):
    
    answer = 0
    dungeons_list = list(permutations(dungeons, len(dungeons))) # 순열을 통해 모든 순서의 던전 리스트 저장
    
    for dungeons in dungeons_list:
        result = gaming(k, dungeons)
        if answer < result:
            answer = result
    
    return answer

1. itertools의 permutations(순열)를 통해 가능한 모든 순서의 던전 리스트를 저장한다.

2. 순서가 정해진 던전 리스트를 통과하는 던전 탐험 함수를 통해 통과한 던전 개수가 가장 많은 값을 구한다.

 

전력망을 둘로 나누기 - 완전탐색, Level2

from collections import deque

'''
두 개 트리 노드 개수 차이 계산 함수
@params: n(송전탑의 개수), wires(하나의 전선이 끊어진 송전탑 전선 리스트)
@return: number (두 전력망이 갖는 송전탑 개수 차이)
'''
def bfs(n, wires):
    
    visits, result = [False] * (n + 1), 0
    q, visits[1] = deque([1]), True # 1부터 연결
    
    while q:
        node = q.popleft()
        for a, b in wires:
            if a == node and visits[b] == False:
                q.append(b)
                visits[b] = True
            if b == node and visits[a] == False:
                q.append(a)
                visits[a] = True
    
    for visit in visits:
        if visit: result += 1 # 하나의 트리가 가지는 노드 수
    
    return abs((n - result) - result) # (나머지 트리가 가지는 노드 수) - (하나의 트리가 가지는 노드 수)


def solution(n, wires):
    answer = 987654321 # INF
    
    for wire in wires:
        tmp_wires = wires * 1
        tmp_wires.remove(wire) # 하나의 전선을 제거
        result = bfs(n, tmp_wires)
        if result < answer:
            answer = result
    
    return answer

1. 하나의 전선을 제거한 전선 리스트를 만든다.

    1.1) 전선은 트리 형태로 연결되어 있기 때문에 하나를 제거하면 두 개의 트리가 만들어진다.

2. BFS를 통해 만들어진 두 개의 트리를 두 개 트리 노드 개수 차이 계산 함수를 통해 계산한다.

3. 반복을 통해 모든 경우를 계산한다.

 

모음사전 - 완전탐색, Level2

def recursion(string, answer):
    
    if string != '': # 빈 문자열은 사전 리스트에 없음
        answer.append(string)
    
    if len(string) < 5:
        recursion(string + 'A', answer)
        recursion(string + 'E', answer)
        recursion(string + 'I', answer)
        recursion(string + 'O', answer)
        recursion(string + 'U', answer)


def solution(word):
    answer = [] # 사전 리스트
    recursion('', answer)
    return answer.index(word) + 1

1. 재귀를 통해 가능한 모든 모음의 사전 리스트를 만든다.

    1.1) 'A', 'E', 'I', 'O', 'U' 순서로 재귀를 호출하기 때문에 리스트는 정렬되어 있다.

2. index 함수를 통해 단어가 몇 번째 단어인지 찾는다.

 

타겟 넘버 - 깊이/너비 우선 탐색(DFS/BFS), Level2

from collections import deque

def solution(numbers, target):
    
    answer, q = 0, deque()
    q.append([numbers[0], 0]) # [index까지 계산한 값, index]
    q.append([-numbers[0], 0])
    
    while q:
        val, idx = q.popleft()
        if idx == len(numbers) - 1: # 모든 numbers를 계산한 경우
            if val == target:
                answer += 1
        else:
            q.append([val + numbers[idx + 1], idx + 1])
            q.append([val - numbers[idx + 1], idx + 1])
    
    return answer

1. numbers 배열의 index까지 개산한 값과 index를 저장한다.

2. 경우는 덧셈/뺄셈 두가지로 경우에 해당하는 값과 index를 모두 저장한다.

3. 모든 numbers를 이용했을 때 값이 target 값과 일치한다면 가능한 경우(정답)가 증가한다.

 

네트워크 - 깊이/너비 우선 탐색(DFS/BFS), Level3

from collections import deque

def solution(n, computers):
    
    visits = [False] * n
    networks = {i: [] for i in range(n)}
    answer = 0
    
    for idx_1, computer in enumerate(computers):
        for idx_2, node in enumerate(computer):
            if node == 1:
                networks[idx_1].append(idx_2)
    
    q = deque()
    for idx, visit in enumerate(visits):
        if not visit:
            visits[idx] = True
            q.append(idx)
            while q:
                node = q.popleft()
                for neighbor in networks[node]:
                    if not visits[neighbor]:
                        visits[neighbor] = True
                        q.append(neighbor)
            answer += 1
    
    return answer

1. 모든 컴퓨터(computers)를 방문한다. (이때 하나의 네트워크로 묶여있다면 방문했다고 본다.)

2. 방문하는 횟수와 네트워크의 개수(정답)는 같다.

 

게임 맵 최단거리 - 깊이/너비 우선 탐색(DFS/BFS), Level2

from collections import deque

def solution(maps):
    
    n, m = len(maps), len(maps[0])
    for i in range(n): # 벽이 없는 자리: 0, 벽이 있는 자리: -1으로 변경
        for j in range(m):
            if maps[i][j] == 1:
                maps[i][j] = 0
            elif maps[i][j] == 0:
                maps[i][j] = -1

    q = deque([[0, 0]])
    maps[0][0] = 1
    nx, ny = [-1, 1, 0, 0], [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        for i in range(4):
            dx, dy = x + nx[i], y + ny[i]
            if 0 <= dx < n and 0 <= dy < m and maps[dx][dy] == 0:
                maps[dx][dy] = maps[x][y] + 1
                q.append([dx, dy])
    
    if maps[n - 1][m - 1] == 0:
        return -1
    return maps[n - 1][m - 1]

1. 미로(maps)를 방문 가능한 자리(0) / 방문 불가능한 자리(-1)로 세팅한다.

2. 시작점([0][0])을 1로 세팅하고 방문 가능한 자리에 최단거리를 세팅한다.

    2.1) 최단거리를 세팅하는 방법으로 BFS를 사용한다.

 

단어 변환 - 깊이/너비 우선 탐색(DFS/BFS), Level3

from collections import deque

def solution(begin, target, words):
    answer = 0
    
    q = deque([(begin, 1)])
    visits, n = [begin], len(begin)
    
    while q:
        now, count = q.popleft()
        if now == target:
            answer = count - 1
            break
        for word in words:
            diff = 0
            for i in range(n):
                if now[i] != word[i]:
                    diff += 1
            if diff == 1 and word not in visits:
                q.append((word, count + 1))
                visits.append(word)
                
    return answer

1. 1개의 알파벳이 다른 단어(now)와 그 단어를 찾기까지 과정의 횟수(count)를 기록한다.

2. 목적한 단어(target)까지 도착하기까지 최소 횟수(정답)을 구한다.

 

여행경로 - 깊이/너비 우선 탐색(DFS/BFS), Level3

from collections import deque

def solution(tickets):
    
    n = len(tickets)
    q = deque([('ICN', ['ICN'], [False] * n)])
    answers = []
    while q:
        now, routes, visits = q.popleft()
        if False not in visits:
            answers.append(routes)
        for idx, (start, end) in enumerate(tickets):
            if start == now and visits[idx] == False:
                temp_visits = visits * 1
                temp_visits[idx] = True
                q.append((end, routes + [end], temp_visits))
    
    answers.sort()
    return answers[0]

1. 돌아올 수 있을때까지의 모든 경로를 저장한다.

    1.1) 저장하는 과정에 BFS를 사용한다. start → end를 큐로 구현한다.

2. 모든 경로 중 알파벳순으로 가장 앞선 경로가 정답이다.

 

가장 먼 노드 - 그래프, Level3

from collections import deque

def solution(n, edge):
    
    answer = 0
    graph = [[] for _ in range(n + 1)]
    visited = [0] * (n + 1) # 1번 노드 기준 각각 거리
    
    # 출발점: 1
    q = deque([1])
    visited[1] = 1
    
    for start, end in edge:
        graph[start].append(end)
        graph[end].append(start)

    # BFS를 통해 1번 노드로부터 거리를 계산
    while q:
        now = q.popleft()
        for element in graph[now]:
            if visited[element] == 0:
                visited[element] = visited[now] + 1
                q.append(element)
    
    # 가장 먼 노드 개수 계산
    max_value = max(visited)
    for i in range(1, n + 1):
        if visited[i] == max_value:
            answer += 1

    return answer

1. 출발점 (1번 노드)를 기준으로 그래프 상의 모든 노드와의 거리를 구한다.

    1.1) 이때 BFS를 사용한다

2. 가장 먼 노드의 값을 통해 가장 먼 노드의 개수(정답)를 구한다.

 

※ 못 푼 문제

1. 아이템 줍기 - 깊이/너비 우선 탐색(DFS/BFS), Level3

2. 퍼즐 조각 채우기 - 깊이/너비 우선 탐색(DFS/BFS), Level3

3. 순위 - 그래프, Level3