두 개의 연결 리스트(Linked List)가 주어졌을 때, 두 리스트에 모두 존재하는 요소 중 첫 번째로 등장하는 공통 요소를 찾아야 하는 경우가 있습니다. 이를 위해 연결 리스트에 요소를 추가하는 메서드와, 두 리스트에서 가장 먼저 나타나는 공통 값을 반환하는 메서드를 정의할 수 있습니다.
아래는 이를 구현한 예제입니다.
예제 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList_structure:
def __init__(self):
self.head = None
self.last_node = None
def add_vals(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def first_common_val(list_1, list_2):
curr_1 = list_1.head
while curr_1:
data = curr_1.data
curr_2 = list_2.head
while curr_2:
if data == curr_2.data:
return data
curr_2 = curr_2.next
curr_1 = curr_1.next
return None
my_list_1 = LinkedList_structure()
my_list_2 = LinkedList_structure()
my_list = input('첫 번째 연결 리스트의 요소를 입력하세요 : ').split()
for elem in my_list:
my_list_1.add_vals(int(elem))
my_list = input('두 번째 연결 리스트의 요소를 입력하세요 : ').split()
for elem in my_list:
my_list_2.add_vals(int(elem))
common_vals = first_common_val(my_list_1, my_list_2)
if common_vals:
print('첫 번째 연결 리스트에서 가장 먼저 나타나며 두 리스트에 공통으로 존재하는 요소는 {}입니다.'.format(common_vals))
else:
print('두 연결 리스트에는 공통 요소가 없습니다')
실행 결과
첫 번째 연결 리스트의 요소를 입력하세요 : 45 67 89 123 45 두 번째 연결 리스트의 요소를 입력하세요 : 34 56 78 99 0 11 두 연결 리스트에는 공통 요소가 없습니다
공통 요소가 존재하는 경우의 실행 결과는 다음과 같습니다.
첫 번째 연결 리스트의 요소를 입력하세요 : 12 34 56 78 90 두 번째 연결 리스트의 요소를 입력하세요 : 55 78 21 34 첫 번째 연결 리스트에서 가장 먼저 나타나며 두 리스트에 공통으로 존재하는 요소는 34입니다.
코드 설명
'Node' 클래스를 생성합니다. 각 노드는 데이터 값(data)과 다음 노드를 가리키는 참조(next)를 가집니다.
필요한 속성을 갖는 'LinkedList_structure' 클래스를 생성합니다.
'__init__' 함수는 첫 번째 요소인 'head'와 마지막 노드인 'last_node'를 'None'으로 초기화합니다.
'add_vals' 메서드는 연결 리스트의 맨 끝에 새로운 값을 추가하는 역할을 합니다.
'first_common_val' 함수는 두 연결 리스트를 순회하면서 가장 먼저 발견되는 공통 값을 찾아 반환하며, 공통 요소가 없으면 None을 반환합니다.
'LinkedList_structure' 클래스의 인스턴스 두 개를 생성합니다.
사용자로부터 입력받은 요소들을 각 연결 리스트에 추가합니다.
두 연결 리스트를 인자로 'first_common_val' 함수를 호출합니다.
반환된 결과에 따라 적절한 메시지를 콘솔에 출력합니다.
시간 복잡도와 최적화 팁
위 방식은 첫 번째 리스트의 각 요소에 대해 두 번째 리스트 전체를 순회하므로, 시간 복잡도는 O(m × n)입니다. 여기서 m과 n은 각각 두 연결 리스트의 길이입니다. 리스트의 길이가 길어지면 성능 저하가 발생할 수 있습니다.
이 경우 두 번째 리스트의 모든 값을 미리 set(집합)에 저장해 둔 뒤, 첫 번째 리스트를 앞에서부터 순회하며 집합에 해당 값이 존재하는지만 확인하면 됩니다. 이렇게 하면 시간 복잡도를 O(m + n)까지 줄일 수 있어 훨씬 효율적입니다.