서로 다른 양의 정수로 구성되어 있고 오름차순으로 정렬된 이중 연결 리스트(doubly linked list)가 있다고 가정해 봅시다. 이때 리스트 안에서 두 노드 데이터의 곱이 주어진 값 x와 같아지는 모든 쌍(pair)을 찾아야 합니다. 여기서 중요한 제약 조건은 추가적인 메모리 공간을 사용하지 않고 문제를 해결해야 한다는 점입니다.
예를 들어, 입력이 L = 1 ↔ 2 ↔ 4 ↔ 5 ↔ 6 ↔ 8 ↔ 9이고 x = 8이라면, 곱이 8이 되는 쌍은 (1, 8)과 (2, 4)이므로 출력은 다음과 같습니다.
(1, 8), (2, 4)
접근 방법
이 문제는 투 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 하나의 포인터는 리스트의 맨 앞(head)에서 시작하고, 다른 포인터는 맨 끝(tail)에서 시작한 뒤, 두 포인터가 서로를 향해 이동하면서 조건을 검사하는 방식입니다. 정렬된 상태를 활용하기 때문에 곱이 목표값보다 작으면 왼쪽 포인터를 앞으로, 크면 오른쪽 포인터를 뒤로 이동시키면 됩니다. 구체적인 알고리즘 단계는 다음과 같습니다.
curr := head, nxt := head로 초기화합니다.
nxt.next가 None이 아닌 동안 nxt := nxt.next를 반복하여, nxt를 리스트의 마지막 노드로 이동시킵니다.
found := False로 초기화합니다.
curr와 nxt가 null이 아니고, 서로 다른 노드이며, nxt.next가 curr가 아닌 동안 다음을 반복합니다.
(curr.data × nxt.data) == x라면:
found := True로 설정합니다.
쌍 (curr.data, nxt.data)를 출력합니다.
curr := curr.next, nxt := nxt.prev로 각각 이동합니다.
그렇지 않다면:
(curr.data × nxt.data) < x라면, 곱을 키워야 하므로 curr := curr.next로 이동합니다.
그 외의 경우에는 곱을 줄여야 하므로 nxt := nxt.prev로 이동합니다.
반복이 종료된 후에도 found가 False라면 "Not found"를 출력합니다.
이 방식은 각 노드를 최대 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 두 개의 포인터만 사용하므로 공간 복잡도는 O(1)입니다.
예제 코드
다음 Python 구현 예제를 통해 더 자세히 이해해 보겠습니다.
class ListNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insert(head, data):
node = ListNode(0)
node.data = data
node.next = node.prev = None
if (head == None):
(head) = node
else :
node.next = head
head.prev = node
head = node
return head
def get_pair_prod(head, x):
curr = head
nxt = head
while (nxt.next != None):
nxt = nxt.next
found = False
while (curr != None and nxt != None and curr != nxt and nxt.next != curr) :
if ((curr.data * nxt.data) == x) :
found = True
print("(", curr.data, ", ", nxt.data, ")")
curr = curr.next
nxt = nxt.prev
else :
if ((curr.data * nxt.data) < x):
curr = curr.next
else:
nxt = nxt.prev
if (found == False):
print( "Not found")
head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
get_pair_prod(head, x)
입력
head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
출력
( 1 , 8 )
( 2 , 4 )