Graph
-
알고리즘) 프로그래머스 Graph, 사이클 제거알고리즘/프로그래머스 고득점 Kit 2020. 5. 1. 15:37
프로그래머스 고득점Kit - Graph 사이클 제거 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 노드의 사이즈를 돌면서 하나씩 제거하고 사이클이 있는지 없는지 체크했다. 결과적으로 정확성 테스트는 다 맞지만, Cycle을 확인하는 메소드를 재귀로 호출하여 효율성은 다 틀린 것 같다. 이후 이 문제를 푼 분들의 로직을 보면서 가장 매력적인 로직을 찾아냈다. 전체 노드의 갯수 -1 개가 되면 사이클이 없다는 것이다. 다만, 컴포넌트의 갯수가 1개가 아닌 2개~n개일 때는 컴포넌트의 갯수도 같이 세줘야 한다는 것이다. 이 로직에 따라 코드를 짜봤지만, ..
-
알고리즘) 프로그래머스 Graph, 순위알고리즘/프로그래머스 고득점 Kit 2020. 4. 27. 16:14
프로그래머스 고득점 Kit - Graph 순위 풀이 (2020.04.27) 문제의 조건에서 경기 결과에 모순이 없으며, A>B, B>C 이면 항상 A>B>C의 순서가 매겨진다고 되어있다. 따라서, 경기 결과가 유실되어도 특정 선수(A)가 이긴 상대들은 A를 이긴 상대들이 이길 수 있다는 뜻이다. 경기 결과 입력 후, 서로 상관관계에 따라 입력을 해주고 랭킹을 부여할 수 있는 선수들을 찾아 return했다. 1. 전체 경기 결과를 이긴 상대 리스트, 진 상대 리스트에 담아준다. (선수 Index에 맞춰서) 2. 서로 경기 결과에 대해 이기고 진 상대들을 업데이트 해준다. 3. 경기 결과가 모두 있는 선수들은 Rank를 부여할 수 있으므로, 전체 경기 결과가 있는 선수들의 수를 return해준다. (2020..