[TIL_Carrotww] 50 - 22/11/11

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 등대 어제 풀던거 다른 방법으로 접근해 보았다.
푼 친구에게 접근 방법만 물어보고 그걸 토대로 풀어보았다.

• 기본 틀

from collections import defaultdict

def solution(n, lighthouse):
    path_dict = defaultdict(list)

    for a, b in lighthouse:
        path_dict[a].append(b)
        path_dict[b].append(a)

    result = 0

위 코드는 안 바뀔 것 같다.
위 코드를 시작으로 해결 방식은
path_dict 딕션어리를 while 문으로 돌며 끝에 노드를 찾아 해당 노드에 물려있는 key 노드를 path_dict에서 지운 후 역 방향으로 가는 것도 지워준다.
위 방법을 반복하면 모든 노드를 지우게 되어 있다.
3번정도 풀어봤는데 시간 초과가 난다ㅜㅜㅜㅜ
그래도 풀이는 올려 본다.

• 첫 번째

    while path_dict:
        for end_node, side_node in path_dict.items():
            if not side_node:
                del(path_dict[end_node])
            if len(side_node) == 1: # val 이 중심, key 가 끝 노드
                del_val = [x for x in path_dict[side_node[0]]] # 끝에 달려있는거 저장
                need_remove_node = side_node[0]
                del(path_dict[side_node[0]]) # 중심 노드 제거 # 1
                for key, val in path_dict.items():
                    if need_remove_node in val:
                        val.remove(need_remove_node)
                result += 1
                break

위 방법 그대로 무식하게 지우며 시작했다.
RuntimeError: dictionary changed size during iteration
for 문 안에서 key값을 지워서 에러가 났다.

• 두 번째 방법

    while path_dict:
        for end_node, side_node in path_dict.items():
            if len(side_node) == 1:
                del_val = [x for x in path_dict[side_node[0]]]
                need_remove_node = side_node[0]
                result += 1
                break
        del_list = []
        if need_remove_node:
            del(path_dict[need_remove_node])
        for key, val in path_dict.items():
            if need_remove_node in val:
                val.remove(need_remove_node)
                if not val:
                    del_list.append(key)
        for dl in del_list:
            del(path_dict[dl])
        need_remove_node = 0

이건 시간 초과가 났다. 난 path_dict.items() 로 딕션어리 자체를 for문으로 돌려 for 문 내부에서 key값을 지울 수 없어 위 코드의 문제를 해결 한 것이다.
하지만 쓸데 없는 코드가 많은지 시간초과가 났다. ㅠㅠ

생각해보니 너무 그대로 진행했다는 생각이 들었다 dict를 따로 빼서 돌려야하는데 돌리는 중에 지워버리면 당연히 안되는데... 무지성 풀이법...
아무튼 계속 잡고있다가 너무 늦어서 오늘은 여까지 하고.. 다음에 다시 복사한걸로 풀어봐야겠다.