99클럽 코테 스터디 16일차 TIL - 비슷한 문제가 생각날 때

문제1 - 부대 복귀 문제링크

문제 설명

양방향 그래프가 주어지고 출발지 노드들과 목적지가 주어질 때, 각 출발지에서 목적지 노드까지의 최단경로 거리를 구하는 문제입니다.

목적지에 도달할 수 없다면 -1입니다.

 

제약조건

노드n: 최대 10만개

간선roads: 최대 50만개

출발지sources: 최대 500개

 

풀이 과정

처음엔 그래프상에서 최단경로 길이를 구하는 문제라서 다익스트라를 사용해서 출발지 노드에서 목적지 노드까지의 최단경로거리를 구했습니다.

 

시행착오1(다익스트라, 실패)

import heapq

def solve(graph, dists, src, dest):
    q = []
    dists[src][src] = 0
    heapq.heappush(q, (0, src))

    while q:
        curDist, curPos = heapq.heappop(q)

        if curDist > dists[src][curPos]:
            continue

        for nxt in graph[curPos]:
            if dists[src][nxt] > curDist + 1:
                dists[src][nxt] = curDist + 1
                heapq.heappush(q, (dists[src][nxt], nxt))
    
    if dists[src][dest] == float('inf'):
        return -1

    return dists[src][dest]
    

    
def solution(n, roads, sources, destination):
    answer = []
    graph = [[] for _ in range(n + 1)]
    for road in roads:
        u, v = road
        graph[u].append(v)
        graph[v].append(u)

    dists = [[float('inf') for _ in range(n + 1)] for _ in range(n + 1)]

    for source in sources:
        if source == destination:
            answer.append(0)
        elif not graph[source]:
            answer.append(-1)
        else:
            res = solve(graph, dists, source, destination)
            answer.append(res)
        
    return answer

 

이후 제출한 결과 몇 개의 테스트케이스에 대해 시간초과가 발생했습니다.

제 풀이의 시간복잡도를 계산해보면, O(len(source) * len(roads)*logn)입니다.

이는 최대 500 * 500000 * 16 = 40억회의 연산이 필요해서 사실상 시간초과가 발생할 수밖에 없습니다.

 

시행착오2(성공)

어떻게 하면 좀 더 빠를지 고민하다가, 문제를 뒤집어서 목적지에서 출발하여 인접 노드를 탐색하면서 최단거리를 갱신하는 방식으로 구현하였습니다.

from collections import deque

def solution(n, roads, sources, destination):
    answer = []
    
    q = deque()

    dists = [float('inf') for _ in range(n + 1)]

    graph = [[] for _ in range(n + 1)]
    for road in roads:
        graph[road[0]].append(road[1])
        graph[road[1]].append(road[0])

    for nxt in graph[destination]:
        q.append((nxt, 1))
        dists[nxt] = 1
    
    while q:
        curPos, cnts = q.popleft()

        if dists[curPos] != cnts:
            continue
        
        for nxt in graph[curPos]:
            if dists[nxt] > cnts + 1:
                dists[nxt] = cnts + 1
                q.append((nxt, dists[nxt]))
        
    for source in sources:
        if source == destination:
            answer.append(0)
        elif dists[source] == float('inf'):
            answer.append(-1)
        else:
            answer.append(dists[source])

    return answer

목적지에서 출발하여 다른 노드들까지의 최단거리만 구하면 되므로 한 번만 다익스트라 알고리즘을 수행하면 됩니다. 그래서 dists 배열을 1차원으로 구현할 수 있었습니다.

 

제출 결과

 

시행착오3(성공)

더 간단한 풀이는 없을까 고민하던 중, 어차피 간선의 가중치는 모두 1이라서 다익스트라를 굳이 사용할 필요가 없겠다라는 생각이 들었습니다. 그래서 일반적인 방문체크를 수행하는 BFS로 풀 수 있겠다고 생각했습니다.

from collections import deque
def solution(n, roads, sources, destination):
    answer = []
    graph = [[] for _ in range(n + 1)]
    for road in roads:
        graph[road[0]].append(road[1])
        graph[road[1]].append(road[0])

    q = deque()
    vis = set()
    q.append((destination, 0))
    vis.add(destination)
    dists = [-1 for _ in range(n + 1)]
    dists[destination] = 0

    while q:
        curPos, cnts = q.popleft()

        for nxt in graph[curPos]:
            if nxt in vis:
                continue
            vis.add(nxt)

            dists[nxt] = cnts + 1
            q.append((nxt, cnts + 1))
    
    for source in sources:
        answer.append(dists[source])

    return answer

목적지에서부터 시작하여 인접 노드를 BFS 탐색하며 최단거리를 구합니다. 이미 방문했던 노드라면 더 빠른 경로가 있었다는 뜻이기 때문에 다시 방문하지 않아도 됩니다.

 

제출 결과

 

dist값을 비교하는 조건 대신 set을 이용해 방문체크를 하기 때문에 더 시간이 적게 걸렸습니다.

 

문제2 - 풍선 터뜨리기 문제링크

문제 설명

각자 고유한 숫자가 적힌 풍선이 일렬로 주어지는데, 인접한 두개의 풍선을 선택하고 그중 하나를 터뜨린 다음, 다시 풍선을 밀어서 빈 공간을 채웁니다.

이 과정을 풍선 하나가 남을 때까지 반복하는데, 풍선을 터뜨릴 때 규칙이 있습니다.

규칙: 일반적으로는 숫자가 더 큰 풍선을 터뜨리되, 단 한 번 숫자가 더 작은 풍선을 터뜨려도 됩니다.

우리가 구해야 할 것은, 모든 경우의 수를 다 체크해보았을 때 최후에 남을 풍선이 될 수 있는 풍선들을 모아 반환하는 것입니다.

 

풀이 과정

처음에 이 문제를 봤을 때는 DFS나 백트래킹같은 재귀함수 형태로 풀어야 할 것 같았습니다. 모든 경우를 다 체크해가면서 확인해야했기 때문입니다. 하지만, 단 한 번 숫자가 더 작은 풍선을 터뜨릴 수 있다는 규칙이 추가됨에 따라 어떻게 코드를 작성해야할지 어려움을 겪었습니다.

그래서 이 방법은 미뤄두고, 특정 풍선이 무조건 죽는 경우를 생각해보았습니다. 최악의 상황을 가정하여 풍선A와 A의 풍선이 계속 대결을 펼친다고 가정하겠습니다. 그럼 A보다 숫자가 큰 풍선은 모두 터질 것입니다. 마침내 A보다 작은 숫자 풍선들만 남을텐데, 이때 풍선A 양쪽에 풍선A보다 작은 숫자가 있다면 이 풍선은 살릴 수 없습니다.

이때 한쪽에만 더 작은 풍선이 있으면 1회용 스킬인 더 작은 숫자풍선 터뜨리기를 하면 되므로 살 수 있습니다. 더 작은 풍선이 한쪽에 2개 이상 있을지라도 그들끼리 터지는 과정속에서 1개만 남게될 것이고 이에 따라 한쪽에 작은 풍선이 1개만 있을 때만 고려해도 됩니다.

def solution(balloons):
    if len(balloons) <= 2:
        return len(balloons)
    
    answer = 2
    n = len(balloons)
    
    leftMin = [0 for _ in range(n)]
    rightMin = [0 for _ in range(n)]
    
    leftMin[0] = balloons[0]
    rightMin[n - 1] = balloons[n - 1]
    
    for i in range(1, n - 1):
        leftMin[i] = min(leftMin[i - 1], balloons[i])
        rightMin[n - i - 1] = min(rightMin[n - i], balloons[n - i - 1])
    
    for i in range(1, n - 1):
        answer += 1 if not (leftMin[i - 1] < balloons[i] and balloons[i] > rightMin[i + 1]) else 0
    
    return answer

 

제출결과

 

문제3 - 호텔 대실 문제링크

 

문제 설명

사람들이 호텔방을 특정 시간동안 사용하고 싶어합니다. 이때 방을 최소개수만 사용해서 사용 요청 리스트를 모두 처리하는 방 개수를 구하면 됩니다.

사용 요청은 [시작시간, 끝나는시간]형태로 주어지며, 끝난 후에는 10분간의 방 정리 시간이 필요해서 끝나고 10분 이후에 다시 해당 방에 손님을 받을 수 있습니다.

 

풀이 과정

우선, 시작시간이 빠르고, 만약 시작시간이 같다면 끝나는시간이 더 빠른 것이 앞에 오도록 정렬해줍니다.

정렬에 앞서, 시간값이 "시:분" 꼴의 문자열 형태로 주어졌기 때문에 해당 시간을 분으로 바꿔주는 toMinutes 함수를 만들어 숫자로 파싱한 후 정렬해주었습니다.

이후, 예약요청을 순회하면서, 현재 사용중인 방들의 끝나는 시간이 담겨 있는 최소힙에서 가장 빨리 끝나는 방을 뽑아봤을 때, 이 방에 들어갈 수 있다면 들어가고, 들어갈 수 없다면 나머지 확인하지 않은 방들은 전부 들어갈 수 없기 때문에 새로운 방을 하나 배정해줍니다.

import heapq

def toMinutes(s):
    temp = s.split(':')
    res = 60 * int(temp[0]) + int(temp[1])
    return res
    
def solution(book_time):
    # : 기준 파싱해서 튜플로 만들어 저장
    # 시작 시간기준 정렬
    # 순회하며 최소힙에 끝나는 시간 넣음
    # 최소힙에 아무것도 없거나 top 시간이 아직 안됐으면 방 하나 추가
    # 시간 됐으면 해당 요소 팝 시키고 추가
    
    for bt in book_time:
        for i in range(len(bt)):
            bt[i] = toMinutes(bt[i])
    
    book_time.sort()
    hq = []
    cnts = 0

    for bt in book_time:
        if not hq:
            cnts += 1
            heapq.heappush(hq, bt[1])
            continue
        
        if bt[0] < hq[0] + 10:
            cnts += 1
        else:
            heapq.heappop(hq)
        heapq.heappush(hq, bt[1])
            
            
    return cnts

 

제출결과

 

총평

까다로운 문제가 많았습니다. 풍선 문제는 예전에 리트코드에서 trapping rain water을 풀면서 leftMax, rightMax를 구해가며 풀었던 기억이 생각나서 풀 수 있었고, 호텔방 문제는 프로세스 스케쥴러나 철로 문제같은 스위핑 문제를 풀어보면서 정렬과 우선순위 큐의 활용에 익숙해져서 풀 수 있었습니다.