99클럽 코테 스터디 25일차 TIL, 프로그래머스 / 순위

🔑 오늘의 학습 키워드 bfs

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/49191

 

from collections import deque

def solution(n, results):
    answer = 0
    left = {i+1 : [] for i in range(n)}
    right = {i+1 : [] for i in range(n)}
    
    for result in results:
        left[result[0]].append(result[1])
        right[result[1]].append(result[0])
    
    def bfs(start,lr):
        queue = deque([start])
        visited =set()
        while queue:
            gwon = queue.popleft()
            for i in lr[gwon]:
                if i not in visited:
                    queue.append(i)
                    visited.add(i)
        return visited
        
        
    for i in range(1,n+1):
        left_mem = bfs(i,left)
        right_mem = bfs(i,right)
        total = left_mem | right_mem # 합집합
        if len(total) == n-1:
            answer += 1
    
    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

단방향 그래프라고 생각을 했다.

 

자기보다 순위가 낮은 사람들과 자기보다 순위가 높은 사람들 모두를 탐색한다면 자신의 순서를 특정할 수 있다고 생각했다.

 

⏰ 예상 시간 복잡도 O(V+E)

제한 사항

선수의 수는 1명 이상 100명 이하입니다.
경기 결과는 1개 이상 4,500개 이하입니다.
results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
모든 경기 결과에는 모순이 없습니다.

 

😎 알고리즘 개요

1. 단방향 그래프를 탐색하기 위해 그래프를 2개로 나눠주었다.

2. bfs를 돌며 자신이 보다 높은 사람들과 낮은 사람들을 모두 찾아주었다.

3. 만난 사람들을 더해줘서 자신을 제외한 n-1인 경우 +1을 해줬다.

 

✅ 오늘의 회고

 - bfs풀이 :)

- 찾아보면 플루이드워셜 풀이도 있따.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL