citizen   3년 전

혼자 직접 이경우 저경우 다 테스트 해봤는데도 틀린경우를 찾지 못했네요.

일단 저는 팀이 있는 학생들의 수를 구하고

전체 학생수에서 구한 값을 빼 주는 방식으로 문제를 접근하였습니다.

Chain함수에서 arr값을 -1로 만드는 것은 해당 학생번호는 이미

들렀기 때문에 다시 방문할 필요가 없다는 것을 표시하기 위한 것입니다.

Chain을 돌다가 arr값(next)이 start(제일 처음 Chain이 시작된 학생번호)와

일치하면 Chain을 멈추고 학생수들을 더합니다. 그 외에 next가 이미 방문한

학생번호라던지(next = -1인 상황) next가 자기자신의 번호와 일치한다면(Chain을 돌고 있는 경우만)

해당 Chain은 잘못된 것이므로 return해버리구요. 그 외에 상황이라면 next를 이용해

다시 Chain을 돌리도록 하였습니다.

zlzmsrhak   3년 전

반례입니다.

citizen   3년 전

흠.. 제 경우에는 

1번 학생이 1->2->3->2로 사이클이 돌기 때문에 1,2,3번 학생 모두를 제외하도록 하였군요.

옳은 방법은 1번만 제외하고 2번학생은 2->3->2로 사이클을 돌아야 하니 답은 1이 되는 건가요?

zlzmsrhak   3년 전

답은 1이 맞습니다만, 옳은 방법이라면 1->2->3->2에서 2->3->2 부분의 사이클을 찾아내야 O(N)에 답을 찾을 수 있습니다.

citizen   3년 전

마지막 조언을 못 봤더라면 한번 더 틀릴뻔했네요..

도움주셔서 정말 감사합니다.

댓글을 작성하려면 로그인해야 합니다.