[알고리즘연습] 추억점수 , 신고결과받기

0507

LV1, https://school.programmers.co.kr/learn/courses/30/lessons/176963

프로그래머스

나의 풀이

# 0507 14:46 - 15:02
# dict mapping 
# 없으면 continue 

def solution(name, yearning, photo):
    mapped = {name:yearning for name, yearning in zip(name, yearning)}

    result = []
    for i in range(len(photo)):
        count = 0
        for j in range(len(photo[i])):
            try:
                count += mapped[photo[i][j]]
            except:
                continue
            
        result.append(count)
    
    return result

 

LV1, 카카오공채2022, https://school.programmers.co.kr/learn/courses/30/lessons/92334

프로그래머스

풀이시간 1시간 , 첫코드 테스트케이스 두개에서 시간복잡도 통과못함

# 첫풀이, 시간복잡도 초과

def solution(id_list, report, k):
    # 중복 미리제거한 report생성
    report = list(set(report))
    # 공백기준 원소나누기
    report = [r.split(' ') for r in report]
    
    # report에서 각 사람별 신고당한 횟수와 누굴 신고했는지 담겨있는 dict
    
    dic = {} # dic[i] = { i:([신고한사람1, 신고한사람2], 본인이 신고당한횟수) }
    for id in id_list: # id[0] =  muzi
        forward = [id_pair[1] for id_pair in report if id_pair[0] == id] 
        
        # forward = ["frodo", "neo"] == id가 신고한사람
        backward = len([id_pair for id_pair in report if id_pair[1] == id])
        dic[id] = (forward, backward)
    
    result = []
    for id in id_list: # id = muzi
        ban = len([cand for cand in dic[id][0] if dic[cand][1] >= k]) # cand = frodo, neo
        result.append(ban)    
    
    
     return result

두번째 풀이 시간복잡도 통과

# 시간복잡도 통과
# forward, backward dict를 따로 만들어서 backward는 각 id마다 관측시 +1되도록 

def solution(id_list, report, k):
    # 중복 미리제거한 report생성
    report = list(set(report))
    # 공백기준 원소나누기
    report = [r.split(' ') for r in report]
    
    # report에서 각 사람별 신고당한 횟수와 누굴 신고했는지 담겨있는 dict
    
    
    forward = {} # forward = [신고한 사람1, 신고한사람2,..]
    backward = {} # backward = 신고당한 횟수 
    for id in id_list:
        forward[id] = []
        backward[id] = 0
    
    for r in report:
        forward[r[0]].append(r[1]) # 누굴 신고했는지 append
        backward[r[1]] += 1 # 신고당한 횟수 +1 
    
    result = []
    for id in id_list: # id = muzi
        ban = len([cand for cand in forward[id] if backward[cand] >= k])
        result.append(ban)    
    
    
    return result