[파이썬 코딩테스트 개념] 1-1. 연결리스트 - 러너

Runner 기법

Runner 기법은 '연결리스트스러운'  풀이를 위해 사용되며

빠른 러너, 느린 러너 2개의 포인터를 이용한다.

• 빠른 러너(fast runner) : 느린 러너보다 2배 앞선다 (두 칸씩 이동)
• 느린 러너(slow runner) : 빠른 러너보다 2배 느리게 나아간다 (한 칸씩 이동)

 

빠른 러너는 연결리스트의 앞쪽의 노드의 절반을 목적에 알맞은 새로운 연결리스트를 만드는데, 

느린 너러는 연결리스트의 뒤쪽의 노드의 절반을 비교를 위해 사용한다.

(흔히 사용하는 투 포인터를 사용하는 것과 이유가 비슷하다)

 

자세한 경우의 수를 살펴보자.

 

 

연결리스트의 노드의 수가 홀수일 때

홀수일 때는 세 가지 경우로 나누어야 한다.

 

① 빠른 러너가 연결리스트의 노드를 방문하는 경우 while(fast_runner!=None):

 

연결리스트의 노드의 수가 홀수일 때 1) 빠른 러너가 연결리스트의 노드를 가리킬 경우

 

 

② 빠른 러너가 연결리스트의 노드를 방문하지 않는 경우(느린 노드가 연결리스트의 가운데 노드를 가리킴)

 

연결리스트의 노드의 수가 홀수일 때 2) 느린 노드가 연결리스트의 가운데 노드를 가리킬 경우

 

 

③ 느린 노드가 연결리스트의 중간 이후 노드부터 마지막 노드를 방문하는 경우 while(slow_runner!=None):

 

연결리스트의 노드의 수가 홀수일 때 3) 느린 러너가 연결리스트의 노드를 가리킬 경우

 

 

연결리스트의 노드의 수가 짝수일 때

짝수일 때는 두 가지 경우로 나누어야 한다.

 

① 빠른 러너가 연결리스트의 노드를 방문하는 경우 while(fast_runner!=None):

 

연결리스트의 노드의 수가 짝수일 때 1) 빠른 러너가 연결리스트의 노드를 가리킬 경우

 

 

② 느린 노드가 연결리스트의 중간 이후 노드부터 마지막 노드를 방문하는 경우  while(slow_runner!=None):

연결리스트의 노드의 수가 짝수일 때 2) 느린 러너가 연결리스트의 노드를 가리킬 경우

 

 

정리연결리스트의 노드의 수가 짝수일 때

⒧ 빠른 러너가 현재 어떤 노드를 방문한 경우 while(fast_runner!=None):

• 느린 러너를 이용해 연산을 위한 새로운 연결리스트 생성

 

⑵ 빠른 러너가 현재 어떤 노드도 방문하지 않는 경우

• 연결리스트의 길이를 확인해서 홀수이면 if(len(linked_list)%2!=0):  
• 느린 러너가 연결리스트의 중앙을 가리키는 것으로 원하는 연산을 위한 조치를 한 뒤, 느린 러너를 다음 노드로 이동

 

⑶ 느린 러너가 현재 어떤 노드를 방문한 경우 while(fast_runner!=None):

• 느린 러너와 만들어진 새로운 연결리스트를 활용해 비교 연산 수행

 

 

러너 사용 알고리즘 문제 예제

[LeetCode]

234. palindrome-linked-list

Palindrome Linked List - LeetCode

문제풀이 https://steady-eschoi.tistory.com/40