이숭간 공부기록
[프로그래머스] 파이썬 _ 순위 본문
728x90
https://programmers.co.kr/learn/courses/30/lessons/49191
문제유형 : 그래프,,라는데 나는 좀 다르게 풀었다.
문제풀이 :
- 나를 이긴사람을 부모노드로 나에게 진 사람을 자식노드로 구분하여 저장
- 나의 부모노드의수 + 자식노드의 수 = n-1이면 나의 위치는 정해진것이 되므로 answer를 1 증가시킨다.
- 이때 나의 앞에 있는 애들 ( 즉 나를 이긴애들) 의 자식에게 내 자식을 추가한다.
- 나의 뒤에있는 애들 ( 즉 나에게 진 애들) 의 부모에게 나의 부모를 추가한다.
정답코드 :
def solution(n, results):
answer = 0
p = [set() for _ in range(n+1)]
c = [set() for _ in range(n+1)]
for r in results:
p[r[1]].add(r[0])
c[r[0]].add(r[1])
for i in range(1,n+1):
for node in p[i]: # i를 이긴 애들 - node
c[node].update(c[i]) # 나의 앞에있는 애들의 자식에게 나의자식을 준다.
for node in c[i]: # i에게 진 애들 - node
p[node].update(p[i]) # 나의 뒤에있는 애들의 부모에게 나의부모를 준다.
for i in range(1, n+1):
if len(p[i])+len(c[i]) == n-1:
answer += 1
return answer
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 파이썬 _ 디스크컨트롤러 (0) | 2021.08.10 |
---|---|
[프로그래머스] SQL고득점킷 _ SELECT (0) | 2021.08.09 |
[프로그래머스] 파이썬 _ 행렬 테두리 회전하기 (0) | 2021.08.03 |
[프로그래머스] 파이썬 _ 게임 맵 최단거리 (0) | 2021.08.03 |
[프로그래머스] 파이썬 _ 조이스틱 (0) | 2021.08.03 |