[알고리즘] 충돌위험 찾기, 가장 많이 받은 선물, 도넛과 막대 그래프

충돌위험 찾기

매우매우 꼬여있는 문제다. 처음 읽을 때는 안 그래보이지만, 막상 시작하면 어떻게 자료구조를 구축하느냐에 따라 매우매우 더러워질 수 있는 여지가 있는 문제다. 그러나 이는 구현의 영역이다.

 

중요한 것을 두 가지 깨달았다.

 

1 dictionary를 iterate 할때는 dictionary의 사이즈를 바꾸면 안된다. 나는 어차피 이미 해당 iteration이 끝나고 반영되기도 하고 list처럼 순서를 신경 쓰는 자료구조가 아니므로 문제없을 줄 알았는데, 이도 안된다는 것을 확인했다.

 

2 파이썬의 공간복잡도 제한은 생각보다 널널하다. 다른 사람의 풀이 중, 이걸 그냥 모든 로봇의 경로를 리스트화 한 다음 - 각 성분은 x,y,ind - 그걸 단순 비교해준 풀이도 있었다. 그렇게 하면 경로가 길어질수록, 로봇이 많아질수록 공간복잡도가 엉망이 되고, 또 나중에 이를 비교할 때 한참 걸리지 않나? 싶었는데, 실제로 계산해보니 제한보다 한참 남았다.

 

성분이 int라고 가정하면, 메모리 사용량은 아래와 같은데, 보통 python의 제한은 128~512MB 정도가 된다.

데이터의 개수 1 => 메모리 4B

데이터의 개수 1,000 => 메모리 4KB

데이터의 개수 1,000,000 => 4MB

 

128MB 이려면 32,000,000개, 512MB라면 1억개가 넘는 것을 수용할 수 있다는 것이다.

 

로봇 수 * 경로 길이 * 이동 횟수 가 최대 값이 100 * 100 * 200 이니까 2,000,000개. 그니까 한참 남는 것...

그니까 brute force라고 할지라도 시간복잡도만 맞으면 어지간하면 다 풀린다는 이야기!

최적의 방법을 구하는 게 어렵다면 이런 식으로도 다 풀수 있다.

 

내 풀이

from collections import defaultdict

def solution(points, routes):    
    res = 0
    
    numbers = dict()
    for i in range(len(points)): numbers[i+1] = [points[i][0]-1, points[i][1]-1]
    
    robots = [[i, numbers[routes[i][0]][0], numbers[routes[i][0]][1], 1] for i in range(len(routes))]
    
    temp_phase = defaultdict(int)
    
    for _, x, y, _ in robots: temp_phase[(x,y)] += 1
    for key in temp_phase:
        if temp_phase[key] >= 2: res += 1
        
    while robots:
        new_robots = []
        temp_phase = defaultdict(int)
        
        for robot, cur_x, cur_y, des_ind in robots:
            if des_ind == len(routes[robot]): continue
            des_x, des_y = numbers[routes[robot][des_ind]]
            
            if cur_x > des_x: cur_x -= 1
            elif cur_x < des_x: cur_x += 1
            elif cur_y > des_y: cur_y -= 1
            else: cur_y += 1
            
            if (cur_x, cur_y) == (des_x, des_y): des_ind += 1
                
            temp_phase[(cur_x,cur_y)] += 1
            new_robots.append([robot, cur_x, cur_y, des_ind])
            
        for key in temp_phase:
            if temp_phase[key] >= 2: res += 1
        
        robots = new_robots
            
    return res

 

 

가장 많이 받은 선물

쉬운 문제.

 

내 풀이

from collections import defaultdict
from collections import Counter
from itertools import combinations

def solution(friends, gifts):    
    points = defaultdict(int)
    count = Counter(gifts)
    
    res = defaultdict(int)
    
    val = 0
    
    for gift in gifts:
        a, b = gift.split()
        points[a] += 1
        points[b] -= 1
    
    for a, b in combinations(friends, 2):
        point = count[a+' '+b] - count[b+' '+a]
        if point > 0: res[a] += 1
        elif point < 0: res[b] += 1
        else:
            if points[a] > points[b]: res[a] += 1
            elif points[b] > points[a]: res[b] += 1
        
        if val < res[a]: val = res[a]
        if val < res[b]: val = res[b]
    
    return val

 

 

도넛과 막대 그래프

어렵지 않은 문제인데, 시간을 많이 잡아먹혔다. 시간을 많이 들여서 최고의 풀이를 내는 것도 좋지만, 일단은 문제를 푸는 게 우선이라는 것을 명심하자. 앞으로는 브레인스토밍을 하되, 가장 빨리 풀 수 있는 거 하나, 최고의 효율성 하나 이렇게 답안을 내는 것을 연습해보자.

def solution(edges):
    number = dict()
    
    main_node = -1
    total_graphs = -1
    pointed = []
    
    for i, o in edges:
        if i not in number: number[i] = [[],[]]
        if o not in number: number[o] = [[],[]]

        if number[o][0]: number[o][0].append(i)
        else: number[o][0] = [i]

        if number[i][1]: number[i][1].append(o)
        else: number[i][1] = [o]
        
    for node in number:
        ins, outs = number[node]
        if not ins and len(outs) > 1:
            main_node = node  # 주인공 노드 발견
            total_graphs = len(outs)    # 전체 그래프 개수 확인
            pointed = outs
            for point in outs: number[point][0].remove(node)
            del number[node]
            break
            
    ilja = 0
    palja = 0
            
    for node in number:
        ins, outs = number[node]
        if not outs: ilja += 1
        elif len(ins) == 2 and len(outs) == 2: palja += 1
    
    return [main_node, total_graphs-ilja-palja, ilja, palja]