Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- N과M
- 운영체제
- 코딩테스트
- level1
- level2
- 다익스트라
- 다이나믹 프로그래밍
- BOJ
- 힙
- 가상메모리
- level3
- BFS
- 수학
- 파이썬
- 가상메모리 관리
- 딕셔너리
- dfs
- 구현
- MYSQL
- 스택
- level0
- 브루트포스
- 백준
- 재귀
- 그리디
- python
- 프로그래머스
- DP
- programmers
- dict
Archives
- Today
- Total
동캄의 코딩도장
프로그래머스 level3 [순위] 파이썬 본문
https://programmers.co.kr/learn/courses/30/lessons/49191
코딩테스트 연습 - 순위
5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
programmers.co.kr
# 프로그래머스 순위
from collections import deque
def solution(n, results):
answer = 0
win = [[] for _ in range(n+1)]
loss = [[] for _ in range(n+1)]
win_check = [0]*(n+1)
loss_check = [0]*(n+1)
visited = [0]*(n+1)
for result in results:
a, b = result
win[a].append(b)
loss[b].append(a)
def win_bfs(node):
q = deque([])
q.append(node)
this_node = node
cnt = 0
while q:
node = q.popleft()
for next_node in win[node]:
if visited[next_node] == 0:
q.append(next_node)
cnt += 1
visited[next_node] = 1
win_check[this_node] = cnt
def loss_bfs(node):
q = deque([])
q.append(node)
this_node = node
cnt = 0
while q:
node = q.popleft()
for next_node in loss[node]:
if visited[next_node] == 0:
q.append(next_node)
cnt += 1
visited[next_node] = 1
loss_check[this_node] = cnt
for i in range(1, n+1):
visited = [0]*(n+1)
win_bfs(i)
visited = [0]*(n+1)
loss_bfs(i)
for i in range(1, n+1):
if win_check[i]+loss_check[i] == n-1:
answer += 1
return answer
![](https://blog.kakaocdn.net/dn/WSndH/btryRSg234V/T14Kol0NjzWkIlMN2x8DH1/img.png)
위의 예시를 보면
선수 | 승리 | 패배 |
1 | 2,5 | |
2 | 5 | 4,3,1 |
3 | 2,5 | 4 |
4 | 3,2,5 | |
5 | 4,3,2,1 |
각 선수 당 승리한 경기 + 패배한 경기의 수의 합이 n-1이면, 그 선수의 순위가 결정된다.
'코테 > 프로그래머스' 카테고리의 다른 글
프로그래머스 level3 [멀리 뛰기] 파이썬 (0) | 2022.04.11 |
---|---|
프로그래머스 level3 [야근 지수] 파이썬 (0) | 2022.04.11 |
프로그래머스 level3 [ 2 x n 타일링] 파이썬 (0) | 2022.04.08 |
프로그래머스 level3 [가장 먼 노드] 파이썬 (0) | 2022.04.08 |
프로그래머스 level3 [여행경로] 파이썬 (0) | 2022.04.08 |