Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 연결 리스트(Linked List)의 요소가 모두 짝을 이루는지 확인하는 방법

단일 연결 리스트(singly linked list)가 주어졌을 때, 리스트에 포함된 모든 요소가 짝수 번 등장하는지, 즉 각 값이 반드시 한 쌍(pair)으로 존재하는지 확인해야 하는 문제입니다.

예를 들어 입력이 [2, 5, 5, 2, 3, 3]이라면, 2·5·3이 각각 두 번씩 나타나므로 출력은 True가 됩니다.

문제 해결 접근 방식: XOR 활용

이 문제는 XOR(배타적 논리합) 연산의 성질을 이용하면 매우 효율적으로 해결할 수 있습니다.

XOR에는 다음과 같은 중요한 특성이 있습니다.

  • 같은 값을 두 번 XOR하면 결과가 0이 됩니다. (a ^ a = 0)
  • 0과 어떤 값을 XOR하면 그 값 자체가 됩니다. (0 ^ a = a)

따라서 연결 리스트의 모든 노드 값을 순서대로 XOR하면, 짝수 번 등장한 값들은 서로 상쇄되어 사라지고, 홀수 번 등장한 값만 결과에 남게 됩니다. 최종 XOR 결과가 0이면 모든 요소가 짝을 이루고 있는 것이며, 0이 아니면 짝을 이루지 못한 요소가 존재한다는 뜻입니다.

알고리즘 단계

  • xor_res = 0으로 초기화하고, current_node를 연결 리스트의 head로 설정합니다.
  • current_node가 None이 아닐 때까지 반복합니다.
    • xor_res에 현재 노드의 값을 XOR합니다.
    • current_node를 다음 노드로 이동합니다.
  • 반복이 끝난 후 xor_res가 0이 아니면 False, 0이면 True를 반환합니다.

이 방법은 추가 메모리 없이(O(1) 공간 복잡도) 리스트를 한 번만 순회하면 되므로 시간 복잡도는 O(n)입니다.

구현 예제 코드

아래는 Python으로 작성한 전체 구현 예제입니다.

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        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 solve(head):
    xor_res = 0
    current_node = head
    while current_node != None:
        xor_res = xor_res ^ current_node.val
        current_node = current_node.next
    return False if xor_res else True

head = make_list([2, 5, 5, 2, 3, 3])
print(solve(head))

입력

[2, 5, 5, 2, 3, 3]

출력

True

주의할 점

XOR 기반 풀이는 간단하고 효율적이지만, 값이 정수일 때만 사용할 수 있다는 제약이 있습니다. 문자열이나 객체처럼 XOR 연산이 불가능한 데이터 타입이라면 딕셔너리나 Counter를 이용해 각 값의 등장 횟수를 세고, 모든 횟수가 짝수인지 검사하는 방식으로 대체해야 합니다.