정렬된 상태에서 K개의 노드만큼 회전된 연결 리스트가 하나 주어집니다. 우리의 목표는 이때의 회전 횟수 K를 구하는 것입니다. 예를 들어, 아래 그림처럼 K개의 노드만큼 회전된 연결 리스트가 입력으로 주어졌다고 가정해 보겠습니다.
그렇다면 원래 리스트는 다음과 같은 형태였을 것입니다.
그림에서 확인할 수 있듯이 여기서 K는 2입니다. 즉, 입력된 연결 리스트는 원래 정렬된 리스트를 2번 회전시킨 결과입니다.
예제로 이해하기
입력 − 리스트: 5 → 7 → 9 → 1 → 3
출력
연결 리스트의 요소: 5 7 9 1 3
정렬 후 회전된 연결 리스트의 회전 횟수: 3
설명 − 원래 정렬된 리스트를 세 번 회전하면 입력 리스트를 얻을 수 있습니다.
1 → 3 → 5 → 7 → 9, 원본 9 → 1 → 3 → 5 → 7, 1회전 7 → 9 → 1 → 3 → 5, 2회전 5 → 7 → 9 → 1 → 3, 3회전
입력 − 리스트: 17 → 25 → 62 → 99
출력
연결 리스트의 요소: 17 25 62 99
정렬 후 회전된 연결 리스트의 회전 횟수: 4
설명 − 원래 정렬된 리스트를 네 번 회전하면 입력 리스트를 얻을 수 있습니다.
17 → 25 → 62 → 99, 원본 99 → 17 → 25 → 62, 1회전 62 → 99 → 17 → 25, 2회전 25 → 62 → 99 → 17, 3회전 17 → 25 → 62 → 99, 4회전
프로그램에 적용된 접근 방식
입력 연결 리스트에는 반드시 '이전 노드보다 값이 작아지는 지점'이 한 곳 존재합니다. 만약 입력 리스트 자체가 이미 정렬된 상태라면, 이는 원본 리스트를 완전히 한 바퀴(리스트 길이만큼) 회전한 것과 같습니다.
헤드 노드부터 시작하여 '현재 노드의 데이터 ≥ 헤드 노드의 데이터'인 동안 리스트를 순회하며 카운트를 증가시키고, '현재 노드의 데이터 < 헤드 노드의 데이터'가 되는 순간 루프를 종료합니다. 이때의 카운트 값이 곧 입력 리스트를 얻기 위해 원본 리스트에서 수행된 회전 횟수가 됩니다.
- 입력 리스트를 생성하고 요소를 삽입합니다.
- insert_node(struct List_Node** head, int data) 함수는 주어진 데이터를 가진 노드를 단일 연결 리스트의 맨 앞에 삽입합니다.
- print(struct List_Node* node) 함수는 while 루프를 사용해 헤드부터 끝까지 연결 리스트의 요소를 출력합니다.
- rotations(struct List_Node* head) 함수는 연결 리스트의 헤드 포인터를 인자로 받아, 입력 리스트를 만들기 위해 원본 리스트에서 수행된 회전 횟수를 반환합니다.
- 카운트(count)를 0으로 초기화합니다.
- temp 변수에 헤드 노드의 데이터 값을 저장합니다.
- while 루프를 통해 연결 리스트의 끝(head != NULL)까지 순회합니다.
- 현재 노드의 데이터가 temp보다 크거나 같으면 count를 증가시킵니다.
- 현재 노드의 데이터가 헤드 노드의 데이터(temp)보다 작으면 루프를 종료(break)합니다.
- 순회가 끝나면 count를 결과값으로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
struct List_Node{
int data;
struct List_Node* next;
};
int rotations(struct List_Node* head){
int count = 0;
int temp = head->data;
while (head != NULL){
if (temp > head->data){
break;
}
count++;
head = head->next;
}
return count;
}
void insert_node(struct List_Node** head, int data){
struct List_Node* new_node = new List_Node;
new_node->data = data;
new_node->next = (*head);
(*head) = new_node;
}
void print(struct List_Node* node){
while (node != NULL){
cout<<node->data<<" ";
node = node->next;
}
}
int main(){
struct List_Node* head = NULL;
insert_node(&head, 2);
insert_node(&head, 1);
insert_node(&head, 18);
insert_node(&head, 35);
insert_node(&head, 28);
cout<<"Elements in the linked list are: ";
print(head);
cout<<"\nCount of rotations in sorted and rotated linked list are: "<<rotations(head);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Elements in the linked list are: 28 35 18 1 2 Count of rotations in sorted and rotated linked list are: 2