시작 노드가 head인 연결 리스트(Linked List)와 두 개의 정수 m, n이 주어졌다고 가정해 보겠습니다. 우리는 리스트를 끝까지 순회하면서 처음 m개의 노드는 유지하고, 그 직후에 이어지는 n개의 노드는 삭제하는 작업을 반복해야 합니다. 이 과정은 연결 리스트의 끝에 도달할 때까지 계속되며, 최종적으로 수정된 연결 리스트를 반환하면 됩니다.
연결 리스트의 노드 구조는 다음과 같이 정의됩니다.
Node
value : <정수>
next : <다음 노드를 가리키는 포인터>예를 들어, 입력이 elements = [1, 2, 3, 4, 5, 6, 7, 8], m = 3, n = 1이라면 출력은 [1, 2, 3, 5, 6, 7]이 됩니다.
동작 방식 이해하기
위 예제에서는 3개의 노드(1, 2, 3)를 유지한 후 바로 다음 노드(4) 하나를 삭제합니다. 이 패턴이 리스트 끝까지 반복되므로, 최종 연결 리스트는 아래와 같은 형태가 됩니다.
1 → 2 → 3 → 5 → 6 → 7
문제 해결 접근 방법
이 문제는 두 개의 포인터(prev, curr)와 카운터 변수를 활용해 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.
- prev와 curr을 모두 head로 초기화합니다.
- 카운터 q와 p를 0으로 설정합니다.
- curr이 null이 아닌 동안 반복합니다.
- q를 1씩 증가시킵니다.
- q가 m과 같아지면, curr을 n번 앞으로 이동시켜 삭제할 구간을 건너뜁니다.
- prev.next를 curr.next에 연결하여 중간 노드들을 제거합니다.
- q를 0으로 초기화해 다음 주기를 준비합니다.
- prev와 curr을 각각 한 칸씩 전진시킵니다.
- 반복이 끝나면 head를 반환합니다.
Python 구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
def solve(head, m, n):
prev = curr = head
q = 0
p = 0
while curr:
q += 1
if q == m:
for i in range(n):
if curr.next is not None:
curr = curr.next
prev.next = curr.next
q = 0
prev = prev.next
curr = curr.next
return head
head = ListNode()
elements = [1, 2, 3, 4, 5, 6, 7, 8]
head = make_list(elements)
res = solve(head, 3, 1)
print_list(res)입력
[1, 2, 3, 4, 5, 6, 7, 8], 3, 1
출력
[1, 2, 3, 5, 6, 7]
마무리
이 알고리즘은 연결 리스트를 한 번만 순회하면서 O(N)의 시간 복잡도로 문제를 해결합니다. 포인터 조작만으로 노드를 삭제할 수 있기 때문에 추가 메모리 사용 없이 효율적으로 처리할 수 있다는 점이 큰 장점입니다. 연결 리스트 문제에서 자주 등장하는 패턴이니, prev와 curr 포인터의 역할을 잘 기억해 두면 다양한 변형 문제에도 쉽게 응용할 수 있습니다.