반복 이동 경로의 시작 지점 찾기
자바스크립트 코딩테스트 문제로 functional-graph-cycle 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
각 지점에서 다음으로 이동할 지점이 최대 하나씩 정해져 있습니다.
정수 배열 next에서 next[i]는 i번 지점 다음에 이동할 지점을 뜻합니다. 더 이상 이동할 수 없는 지점은 -1로 표시됩니다.
start 지점에서 출발해 next를 따라 계속 이동할 때, 언젠가 이미 방문한 지점으로 다시 들어가 반복 경로가 생긴다면 그 반복이 처음 시작되는 지점 번호를 반환하는 findLoopEntryStation 함수를 작성하세요.
반복 경로 없이 -1에 도착하면 -1을 반환합니다.
제한사항
1 <= next.length <= 1000000 <= start < next.lengthnext[i]는-1이거나0이상next.length - 1이하인 정수입니다.- 반환값은
start에서 도달 가능한 반복 경로의 시작 지점입니다. - 반복 경로가 없다면
-1을 반환합니다.
예시
- 입력:
next = [1, 2, 3, 1],start = 0-> 출력:1 - 입력:
next = [1, 2, -1],start = 0-> 출력:-1 - 입력:
next = [0, 2, 3, 1],start = 0-> 출력:0 - 입력:
next = [2, 0, 4, 4, 3],start = 1-> 출력:4
힌트
- 방문 여부를 Set에 저장하면 쉽게 풀 수 있지만, 포인터 2개만으로도 반복 시작점을 찾을 수 있습니다.
- 느린 포인터는 한 칸, 빠른 포인터는 두 칸씩 이동해 보세요.
- 두 포인터가 만난 뒤에는 한 포인터를
start로 되돌리고, 둘 다 한 칸씩 움직이면 반복 시작점에서 다시 만납니다.
해설
이 문제는 각 지점에서 나가는 간선이 하나뿐인 그래프, 즉 functional graph에서 사이클 진입점을 찾는 문제입니다.
먼저 느린 포인터 slow는 한 번에 한 칸, 빠른 포인터 fast는 한 번에 두 칸씩 움직입니다. 반복 경로가 있다면 빠른 포인터가 언젠가 느린 포인터를 따라잡습니다. 반대로 이동 중 -1을 만나면 더 이상 갈 수 없으므로 사이클은 없습니다.
두 포인터가 처음 만난 지점이 반드시 반복의 시작점은 아닙니다. 예를 들어 0 -> 1 -> 2 -> 3 -> 1에서는 포인터들이 사이클 내부 어딘가에서 만날 수 있지만, 반복이 시작되는 지점은 1입니다.
사이클 진입점을 찾으려면 포인터 하나를 다시 start에 두고, 다른 포인터는 만난 지점에 둡니다. 이제 두 포인터를 모두 한 칸씩 이동시키면 두 포인터가 처음 같아지는 지점이 반복 경로의 시작점입니다.
풀이 순서는 다음과 같습니다.
slow와fast를 모두start로 둡니다.fast가 두 칸 이동할 수 있는 동안slow는 한 칸,fast는 두 칸 이동합니다.- 두 포인터가 같아지면 사이클이 존재합니다.
- 한 포인터를
start로 되돌리고 두 포인터를 한 칸씩 이동합니다. - 다시 만나는 지점을 반환합니다.
- 중간에
-1을 만나면 반복 경로가 없으므로-1을 반환합니다.
각 지점은 포인터 이동 과정에서 상수 횟수만 지나가므로 시간 복잡도는 O(n)입니다. 방문 집합을 쓰지 않고 포인터 변수만 사용하므로 추가 공간 복잡도는 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.