Jinho Tech

풀이

파이썬 내장함수 replace를 사용하면 아주 쉽게 풀 수 있다.  

def solution(s):
    li = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
    for i in range(10):
        s = s.replace(li[i], str(i))
    
    return int(s)

전에는 알고리즘 문제를 설렁설렁 어떻게든 풀기만 하는 느낌으로 넘어갔었는데, 이번에는 다시 공부한다는 생각으로

프로그래머스 문제들을 풀어보려고 한다.

클린코드도 복습하는 겸 나름 최대한 보기 좋게 짜보려고 한다.

풀이)

1. 거리를 구하기 위해서 우선 1: [0,0], 2:[0, 1] ... 9:[2, 2], 0:[3, 1]과 같이 숫자를 좌표로 변환해준다.

 2. 숫자와 왼손, 오른손과의 거리를 구한다.

3. 그 이후는 각 상황에 맞게 ans에 'L', 'R'을 더하고 왼손과 오른손의 위치를 업데이트해주면 된다.

1, 4, 7 -> 왼손, 3, 6, 9 -> 오른손, 2, 5, 8, 0 -> 왼손과 오른손 중 가까운 손

def get_idx(n):
    n = 10 if n == 0 else n-1
    
    return [n//3, n%3]

def get_distance(n1, n2):
    d1, d2 = get_idx(n1), get_idx(n2)
    d = abs(d1[0] - d2[0]) + abs(d1[1] - d2[1])

    return d
    
def get_nexthand(left, right, num, hand):
    if num in [1, 4, 7]:
        return 'left'
    elif num in [3, 6, 9]:
        return 'right'
    else:
        dl = get_distance(left, num)
        dr = get_distance(right, num)
        if dl < dr:
            return 'left'
        elif dl > dr:
            return 'right'
        elif dl == dr:
            return hand
    
def solution(numbers, hand):    
    left, right = 10, 12
    ans = ''
    
    for num in numbers:
        nexthand = get_nexthand(left, right, num, hand)
        if nexthand == "left":
            left = num
            ans += 'L'
        else:
            right = num
            ans += 'R'
    
    return ans

begin에서 target으로 가는 최단경로의 길이를 찾는 문제이다.

두 단어의 차이가 한 글자면 이동 가능하다. 이동 가능한지 판별하는 부분은 아래의 조건문같이 구현했다.

if len([1 for i in range(N) if node[i] != n[i]]) != 1:

dfs를 사용해서 이동 가능한 모든 경로를 다 돌아보고 현재 node가 target이라면

res리스트에 지나왔던 경로의 길이를 append해준다. 마지막에 min(res)를 반환해주면 끝이다.

def solution(begin, target, words):
    def dfs(cnt, node, li, route):
        if node == target:
            res.append(cnt)
        for i, n in enumerate(li):
            if len([1 for i in range(N) if node[i] != n[i]]) != 1:
                continue
            li.pop(i)
            dfs(cnt+1, n, li, route+[n])
            li.insert(i, n)
            
    if target not in words:
        return 0
    
    N = len(begin)
    res = []
    dfs(0, begin, words, [begin])
    
    return min(res) if res else 0

간단한 그래프 탐색 문제이다. 반복문을 돌면서 체크가 안된 노드가 있다면 ans += 1을 하고

그 노드부터 시작하여 dfs 또는 bfs를 돌려서 갈 수 있는 길을 다 체크해주면 된다.

check[i] = 0 -> i 노드 들린 적 없음 -> 탐색 시작

check[i] = 1 -> i 노드 들린 적 있음 -> 탐색 X 

보아하니 백준 실버 4 ~ 실버 2 정도가 프로그래머스 Level 3이랑 비슷한 것 같다.

DFS 풀이

def solution(n, computers):
    def dfs(node):
        if graph[node] and check[node] == 0:
            check[node] = 1
            for n in graph[node]:
                dfs(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            dfs(i)
            ans += 1

    return ans

BFS 풀이

from collections import deque

def solution(n, computers):
    def bfs(node):
        q = deque([node])
        while q:
            node = q.popleft()
            if graph[node] and check[node] == 0:
                check[node] = 1
                for n in graph[node]:
                    q.append(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            bfs(i)
            ans += 1

    return ans

리스트가 아닌 딕셔너리로 그래프를 구현해서 풀어야되는 문제이다.

올바른 경로를 찾을 때까지 뺑뺑이를 돌려줘야 되는 문제라 dfs로 풀었다. 

핵심은 dfs 함수를 재귀로 넘기기 전에 딕셔너리의 value값을 삭제하고 재귀후에 다시 추가해주는 부분같다.

처음에 이 부분을 잘못 생각해서 푸는데 오래걸렸다... 

from collections import defaultdict

def dfs(N, graph, route, node):
    if len(route) == N+1:
        return route
    for i, n in enumerate(graph[node]):
        graph[node].pop(i)
        ret = dfs(N, graph, route+[n], n)
        graph[node].insert(i, n)
        if ret:
            return ret
        
def solution(tickets):
    N = len(tickets)
    graph = defaultdict(list)
    for s, e in tickets:
        graph[s].append(e)
    for k in graph:
        graph[k].sort()
    
    route = dfs(N, graph, ["ICN"], "ICN") 
    return route

추가로 defaultdict라는 친구에 대해 알게되었다.

여태까지 딕셔너리에 값을 채울 때나 키값이 있는지 조건문으로 확인할 때 get을 사용해서 따로 처리하곤

했었는데, defaultdict를 사용하면 오류 걱정없이 그냥 넣어주고 확인하면 된다! 

순위를 정확하게 매길 수 있는 사람이 몇 명인지 찾는 문제이다.

플로이드 와샬 알고리즘을 모른다면 풀기 조금 힘들 것 같은 문제이다. 

플로이드 와샬을 사용해서 최단경로가 아닌 승패를 확인해주면 된다.  

EX)

graph[0][1] = 1 -> 1가 2를 이김

graph[4][3] = -1 -> 4가 5를 이김

graph[1][2] = 0 -> 2와 3의 승패를 알 수 없음 

def solution(n, results):
    graph = [[0]*n for i in range(n)]
    for a, b in results:
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = -1
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] == 1 and graph[k][j] == 1:
                    graph[i][j] = 1
                if graph[i][k] == -1 and graph[k][j] == -1:
                    graph[i][j] = -1
    
    ans = 0
    for li in graph:
        if li.count(0) == 1:
            ans += 1
    return ans

1번 노드에서 제일 먼 노드가 몇 개 인지 찾는 문제이다. 

BFS로 아주 쉽게 풀 수 있다.

from collections import deque

def solution(N, edge):
    graph = [[] for _ in range(N+1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    q = deque([1])
    check_li = [-1]*(N+1)
    check_li[1] = 0
    while q:
        node = q.popleft()
        for n in graph[node]:
            if 0 < n <= N and check_li[n] == -1:
                q.append(n)
                check_li[n] = check_li[node] + 1
                    
    ans = check_li.count(max(check_li))
    return ans