이번 문제의 목표는 중복된 요소를 포함하는 주어진 연결 리스트에서 최소 빈도(minimum frequency)를 가지는 요소의 개수를 세는 것입니다.
연결 리스트(Linked List)는 데이터를 순차적인 순서로 저장하는 자료구조로, 마치 목록처럼 각 요소가 다음 요소와 연결된 형태를 띱니다.
여기서 요소의 빈도(frequency)란 해당 요소가 연결 리스트 안에 등장하는 횟수를 의미합니다. 즉, 이 문제에서는 리스트 전체에서 가장 낮은 빈도를 찾고, 그 빈도에 해당하는 요소들의 개수를 계산해야 합니다.
예를 들어 1, 1, 3, 1, 3, 4, 6으로 이루어진 연결 리스트가 있다고 가정해 봅시다. 이때 최소 빈도는 1이며, 최소 빈도를 가지는 요소는 4와 6 단 두 개뿐이므로 결과값은 2가 됩니다.
입력 −
linked list 1->1->2->2->2->3->3
출력 −
count is 2
설명 −
위 예제에서 최소 빈도는 2이며, 이 빈도를 가지는 요소는 1과 3 두 개입니다. 따라서 개수는 2가 됩니다.
입력 −
linked list = 1->2->3->2->4->2->5
출력 −
count is 4
설명 −
위 예제에서 최소 빈도는 1이며, 이 빈도를 가지는 요소는 1, 3, 4, 5 총 네 개입니다. 따라서 개수는 4가 됩니다.
프로그램에 적용된 접근 방식
연결 리스트를 정의하고 요소들을 삽입(push)합니다.
최소 빈도를 가지는 요소의 개수를 구하는 minimum 함수 안에서, 각 숫자의 빈도를 저장하기 위한 맵(map) "mymap"을 선언합니다.
리스트를 처음부터 끝까지 순회하면서 각 요소의 빈도(등장 횟수)를 mymap에 기록합니다.
모든 빈도를 mymap에 저장한 뒤, 그중 최솟값을 찾습니다.
mymap에서 최소 빈도에 해당하는 항목의 개수를 셉니다.
계산된 개수를 반환합니다.
예제
#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
struct Node {
int key;
struct Node* next;
};
// 스택에 값을 삽입하는 함수
void push(struct Node** head_ref, int new_key){
struct Node* new_node = new Node;
new_node->key = new_key;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// 연결 리스트에서 최소 빈도 요소의 개수를 세는 함수
int minimum(struct Node* head){
// 모든 노드의 빈도를 저장
unordered_map<int, int> mymap;
struct Node* current = head;
while (current != NULL){
int value = current->key;
mymap[value]++;
current = current->next;
}
// 최소 빈도 찾기
current = head;
int min = INT_MAX, count = 0;
for (auto it = mymap.begin(); it != mymap.end(); it++){
if (it->second <= min){
min = it->second;
}
}
// 최소 빈도를 가지는 요소의 개수 세기
for (auto it = mymap.begin(); it != mymap.end(); it++){
if (it->second == min){
count += (it->second);
}
}
return count;
}
int main(){
/* 빈 리스트로 시작 */
struct Node* head = NULL;
int x = 21;
push(&head, 30);
push(&head, 50);
push(&head, 61);
push(&head, 40);
push(&head, 30);
cout <<"count is: "<<minimum(head) << endl;
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 −
count is: 3