Py) 프로그래머스 49191

 

https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

그래프 문제에 들어가있어서 무조건 bfs dfs로 풀려고 했는데 찾아보니까 다들 set 같은 걸 이용해서 풀었다.

그래프 식 코드는 아침에 찾아보자.

스스로 칭찬 하나 - dfs bfs 극혐했는데, 접근이 좋아졌다는 점. 

 

* Floyd-Warshall 알고리즘 적용 (DP)

def solution(n, results):
    answer = 0
    beat = [[None for _ in range(n+1)] for _ in range(n+1)]  # 승패 확인이 되지 않은 상태

    for win, lose in results:       # 승패를 입력함
        beat[win][lose] = True
        beat[lose][win] = False

    #floyd-warshall 식 접근
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if beat[i][j] == None:      # 승패가 확인되지 않았다면 넘김
                    continue
                if beat[j][i] == beat[i][k]:
                    beat[j][k] = beat[i][k]
                    beat[k][j] = not beat[i][k]

    for l in range(1, n+1):
        if None in beat[l][1:l] + beat[l][l+1:]:       # 자기 자신을 제외하고 고려해봄
            continue
        answer += 1

    return answer

if None in beat[l][1:l] + beat[l][l+1:]에서

+ 대신 and를 썼다가 값이 다르게 나와서 보니까, and를 적용하면 한쪽에 None이 있을 경우 조건식이 false가 돼서 answer에 추가가 되어버림.

파이썬에서도 and or 연산자는 조심하자;

 

* 다른 코드

from collections import defaultdict
def solution(n:int,results:list)->int:
    answer = 0
    winners, losers = defaultdict(set), defaultdict(set)    # 중복을 제거하는 딕셔너리 자료형

    for win, lose in results:       # 이긴사람과 진 사람 항목 따로 만들기
        winners[win].add(lose)
        losers[lose].add(win)

    for i in range(1, n+1):
        for winner in losers[i]:
            winners[winner].update(winners[i])      # ...?
        for loser in winners[i]:
            losers[loser].update(losers[i])

    for j in range(1, n+1):
        if len(winners[j]|losers[j]) == n-1:
            answer +=1

    return answer

함수를 저렇게 적는 걸 처음봤다. 오오..

len(win[i]|lose[i])에서 |이 뭔가 하고 한참 찾아봄 - 파이썬에서 bit 연산임

이 부분이 이해가 잘 안됐었음

 for i in range(1, n+1):
        for winner in losers[i]:
            winners[winner].update(winners[i])      # ...?
        for loser in winners[i]:
            losers[loser].update(losers[i])

힘에 의해 winner가 이긴 애들은 다 이긴다는데, 저걸 왜 저렇게 할까 싶어서 이해하는데 오래걸림

그러다가 문뜩 깨달음.. winner와 loser는 같은 애들이라는 걸 잊고 있었음.

그니까 각 인덱스 값이 loser와 winner가 다른게 아니라, 같은 애들인데 승패에 따라 dict를 만들어 놓았던 것.

 

* 

Floyd-Warshall: https://blog.naver.com/ndb796/221234427842

defaultdict: https://dongdongfather.tistory.com/69

bit 연산: | , ^

 

+

개오래걸렸다.

아 맞다 알고리즘! 하고 문제 잡기 시작한게 9시인데, 중간에 한번 졸려서 자긴 했지만 이거 쓰는 시점이 12:46am임 ㅎ.. 오래 걸림..

문제 풀어보는 것보다 다른 사람 코드 보고 이해하고 모르는거 찾아보고 하는게 너무 오래걸림

중간에 현타와서 그런 생각도 했다. 아.. 김예원 알고리즘에 소질 없냐.. 이러고 있는데 김예원이 개발자 취업하면 그건 진짜 하나님이 만들어주신 기적이다 라고...

지치긴 하지만 결국 다 이해했을 때 마음이 너무 편안해서.. ㅋㅎ,,

오래 걸리더라도 이렇게 하는게 맞는걸까 싶다. 점점 빨라지겠지

일단 무슨 방법이든 해보는 것으로...!

사진은 나 자신이 대견스러우니까^0^