[Hackerrank] 1Week + Day6 - BFS

Day 6 Interview Questions | HackerRank

 

1. 문제

BFS를 이용해 정해진 출발점에서 다른 노드들까지의 거리를 노드 순서에 따라 배열에 담은 후 반환해주면 되는 문제입니다.

 

2. 풀이

문제의 제목에서도 알 수 있듯이, BFS(너비 우선 탐색)을 사용하면 쉽게 풀 수 있는 문제입니다.

 

3. 코드

Python

def bfs(n, m, edges, s):
    # Write your code here
    maps = [[False] * n for _ in range(n)]
    for start, end in edges:
        maps[start-1][end-1] = True
        maps[end-1][start-1] = True
        
    result = [-1] * n
    q = []
    visited = [False] * n
    q.append((s-1,0))
    visited[s-1] = True
    
    while q:
        node, distance = q.pop(0)
        result[node] = distance
        
        for i, e in enumerate(maps[node]):
            if e and not visited[i]:
                visited[i] = True
                q.append((i, distance+6))
    del result[s-1]
    return result

 

4. Day 6 추가 문제

4.1 Simple Text Editor

별도의 알고리즘 없이, 문자열을 가지고 주어진 연산을 수행해주면 해결되는 문제입니다. 🤗

Undo 기능을 구현하기 위해서 Stack 자료구조를 사용하였습니다.

s = ''
history = []

def operator(type, value):
    global s
    if type == '1': #append
        s += value
    elif type == '2': #delete
        pos = -int(value)
        s = s[:pos]
    else: #print
        print(s[int(value)-1])

q = int(input())
for _ in range(q):
    op = input().split()
    if op[0] == '4': #undo
        type, value = history.pop()
        operator(type, value)
    else:
        type, value = op[0], op[1]
        if type == '1': history.append(('2', len(value)))
        if type == '2': history.append(('1', s[-int(value):]))
        operator(type, value)

 

4.2 Jesse and Cookies

가장 작은 쿠기 2개를 빼고 이를 더한 후 다시 추가해주는 형식이므로 우선순위 큐 자료구조가 알맞다 생각해 이를 사용하였습니다. 🌹

def cookies(k, A):
    # Write your code here
    q = []
    for a in A: heappush(q, a)
    
    time = 0
    while len(q) > 1 and q[0] < k:
        a, b = heappop(q), heappop(q)
        heappush(q, a+2*b)
        time+=1
    return -1 if q[0] < k else time