반응형
49188
-
알고리즘) 프로그래머스 Graph, 사이클 제거알고리즘/프로그래머스 고득점 Kit 2020. 5. 1. 15:37
프로그래머스 고득점Kit - Graph 사이클 제거 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 노드의 사이즈를 돌면서 하나씩 제거하고 사이클이 있는지 없는지 체크했다. 결과적으로 정확성 테스트는 다 맞지만, Cycle을 확인하는 메소드를 재귀로 호출하여 효율성은 다 틀린 것 같다. 이후 이 문제를 푼 분들의 로직을 보면서 가장 매력적인 로직을 찾아냈다. 전체 노드의 갯수 -1 개가 되면 사이클이 없다는 것이다. 다만, 컴포넌트의 갯수가 1개가 아닌 2개~n개일 때는 컴포넌트의 갯수도 같이 세줘야 한다는 것이다. 이 로직에 따라 코드를 짜봤지만, ..