Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 연결 리스트에서 첫 번째 비반복 원소 찾는 방법

문제 개요

이 문제에서는 크기가 N인 연결 리스트(LL)가 주어지며, 우리의 목표는 연결 리스트에서 첫 번째로 중복되지 않는(non-repeating) 원소를 찾는 프로그램을 작성하는 것입니다.

연결 리스트(linked list)는 노드들이 링크(포인터)를 통해 차례로 연결된 선형 자료구조입니다. 각 노드는 실제 데이터와 다음 노드를 가리키는 참조 값으로 구성됩니다.

예제로 문제 이해하기

입력: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5
출력: 1

설명 −

이 연결 리스트에서 한 번만 등장하는 원소는 1과 5입니다. 두 원소 중 1이 더 앞쪽에 위치하므로 정답은 1이 됩니다.

해결 접근 방법

이 문제는 해시 테이블(hash table)을 활용하면 효율적으로 해결할 수 있습니다. 해시 테이블에는 각 원소와 그 등장 빈도를 함께 저장하며, 구체적인 절차는 다음과 같습니다.

  1. 연결 리스트를 처음부터 끝까지 순회하면서 각 원소의 등장 횟수를 해시 맵에 기록합니다. 처음 등장하는 원소는 빈도 1로 삽입하고, 이미 존재하는 원소라면 빈도를 1씩 증가시킵니다.
  2. 순회가 완료되면 연결 리스트를 다시 앞에서부터 탐색하면서, 해시 맵에서 빈도가 1인 첫 번째 원소를 찾아 반환합니다.
  3. 모든 원소가 두 번 이상 등장한다면 -1을 반환하여 조건을 만족하는 원소가 없음을 나타냅니다.

복잡도 분석: 연결 리스트를 최대 두 번 순회하므로 시간 복잡도는 O(N)이고, 해시 맵에 최대 N개의 원소를 저장하므로 공간 복잡도 역시 O(N)입니다.

C++ 구현 예제

다음 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   struct Node* next;
};
void push(struct Node** head_ref, int new_data){
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
int findFirstNonRepLL(struct Node *head){
   unordered_map<int, int> freqMap;
   for (Node *temp=head; temp!=NULL; temp=temp->next){
      freqMap[temp->data]++;
   }
   for (Node *temp=head; temp!=NULL; temp=temp->next){
      if (freqMap[temp->data] == 1){
         return temp->data;
      }
   }
   return -1;
}
int main(){
   struct Node* head = NULL;
   push(&head, 5);
   push(&head, 6);
   push(&head, 2);
   push(&head, 1);
   push(&head, 4);
   push(&head, 2);
   push(&head, 6);
   push(&head, 4);
   cout<<"연결 리스트의 첫 번째 비반복 원소는 "<<findFirstNonRepLL(head);
   return 0;
}

실행 결과

연결 리스트의 첫 번째 비반복 원소는 1