이 튜토리얼에서는 주어진 연결 리스트(Linked List)에서 피크 요소(Peak Element)를 찾는 프로그램을 작성해 보겠습니다.
피크 요소란 인접한 요소들보다 값이 큰 요소를 의미합니다. 그럼 문제를 해결하는 단계를 하나씩 살펴보겠습니다.
문제 해결 접근 방법
연결 리스트를 위한 구조체 노드(struct Node)를 생성합니다.
더미 데이터로 연결 리스트를 만듭니다.
연결 리스트가 비어 있거나 길이가 1인 경우와 같은 기본 케이스(base case)를 먼저 처리합니다.
첫 번째 요소를
previous변수에 저장합니다.연결 리스트를 순회하면서 다음을 확인합니다.
현재 요소가 이전 요소와 다음 요소보다 큰지 검사합니다.
조건이 만족되면 해당 값을 즉시 반환합니다.
조건이 맞지 않으면 이전 요소(
previous) 값을 현재 값으로 갱신합니다.
순회가 끝나면 결과를 출력합니다.
예제 코드
그럼 실제 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void insertNewNode(struct Node** head_ref, int new_data) {
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
*head_ref = new_node;
}
int findPeakElement(struct Node* head) {
if (head == NULL) {
return -1;
}
if (head->next == NULL) {
return head->data;
}
int prev = head->data;
Node *current_node;
for (current_node = head->next; current_node->next != NULL; current_node = current_node->next) {
if (current_node->data > current_node->next->data && current_node->data > prev) {
return current_node->data;
}
prev = current_node->data;
}
if (current_node->data > prev) {
return current_node->data;
}
return -1;
}
int main() {
struct Node* head = NULL;
insertNewNode(&head, 7);
insertNewNode(&head, 4);
insertNewNode(&head, 5);
insertNewNode(&head, 2);
insertNewNode(&head, 3);
cout << findPeakElement(head) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
5
동작 원리 살펴보기
위 예제에서 연결 리스트는 3 → 2 → 5 → 4 → 7 순서로 구성됩니다. 코드는 두 번째 노드부터 마지막에서 두 번째 노드까지 순회하면서 현재 노드의 값이 앞뒤 노드의 값보다 모두 큰지 확인합니다. 이 예제에서는 값 5가 앞의 2보다 크고 뒤의 4보다 크므로 피크 요소로 판별되어 출력됩니다.
참고로 피크 요소는 여러 개 존재할 수 있으며, 이 알고리즘은 처음 발견된 피크 요소를 반환합니다. 또한 리스트가 비어 있거나 피크 요소가 없는 경우에는 -1을 반환하도록 처리했습니다.
마무리
이번 튜토리얼에서는 연결 리스트에서 피크 요소를 찾는 방법을 알아보았습니다. 시간 복잡도는 리스트를 한 번만 순회하므로 O(n)입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.