HackerRank 라는 온라인 코딩 연습 사이트가 있다.

여기의 문제를 풀어보고 어떻게 풀었는가에 대한 설명과 소감 그리고 배운점을 글로 (꾸준히) 남겨볼까 한다. 나는 평범한 개발자이기에 아마 고민고민끝에 겨우 풀어내고 난 뒤 다른 사람들의 모범답안을 보고 감탄하는 패턴으로 흘러가지 않을까 싶다 ㅋㅋ

Linked Lists: Detect a Cycle

“Easy” 로 분류된 간단한 문제부터 풀어봤다.  간단한 구조로 만들어진 링크드 리스트의 사이클을 탐지해 내는 코드를 만드는 것이다. 사이클이 있으면 true, 없으면 false를 리턴하는 함수를 만들면 된다.

제약조건은 리스트 사이즈는 최소 0부터 최대 100까지.

다음과 같이 풀어보았다.

사이클이 없는 링크드리스트라면 링크의 최대 개수는 노드의 최대 개수 – 1 일 것이다. 이 문제에선 제약조건으로 노드의 최대 개수는 100으로 되어있기 때문에 노드를 쭉 순회하면서 링크의 개수를 세다가 링크의 개수가 100이 되는 순간 사이클이 있다고 판단하도록 만들었다.

처음부터 이렇게 전략을 짜서 코딩 하진 못했고 이렇게 저렇게 코드를 만들다 보니 이런 해법을 찾게 되었다. 다 풀고(사이트 판정을 모두 통과) 나서 들었던 생각은 만약 노드 개수 제약조건이 없거나 매우 클 경우엔 문제가 있지 않을까 하는 생각이 들었다. 그러면서 다른 사람들은 어떻게 풀었을까 Disscussion을 보고 역시나.. 생각지도 못한 방법으로 풀어낸 멋진 답들이 있었다.

천천히 하나씩 노드를 순회하는 포인터와 한번에 두개씩 빠르게 노드를 순회하는 포인터를 계속 비교하다 보면 사이클이 있다면 언젠가는 두 포인터가 가리키는 노드가 같을것이다라는 일종의 “토끼와 거북이” 알고리즘이 인상적이었다. 찾아보니 토끼와 거북이 알고리즘은 사이클 탐지의 꽤 고전적인 알고리즘이었다. (관련링크: https://en.wikipedia.org/wiki/Cycle_detection https://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work-How-does-moving-the-tortoise-to-the-beginning-of-the-linked-list-while-keeping-the-hare-at-the-meeting-place-followed-by-moving-both-one-step-at-a-time-make-them-meet-at-starting-point-of-the-cycle)

쉬운 문제였지만 막상 처음 풀땐 마냥 쉽게 느껴지지는 않았던거 같고 풀고 나서도 더 생각해볼 점과 배워볼만한 여지를 제공해줬던 문제였다. 괜찮았다.