과반수 찾기 알고리즘

수가 다음과 같이 있다고 가정해보자.

3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2

이때 과반수가 넘는 수는 '1'임을 알 수 있다.

과반수가 넘는 수를 찾는 방법에는 다양한 알고리즘이 존재하는데 한번 생각해보자.

1. O(N^2)

부르트포스를 이용하여 문제를 풀되 자신보다 뒤에 나오는 수가 있다면 카운팅해주며 과반수인지 파악해준다.

말그대로 최악의 방법이다.

2. O(NlgN)

정렬을 하고 난 후, 그대로 순차적으로 읽어가며 카운팅을 해주면 된다.

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int arr[100];
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    sort(arr, arr + n);
 
    int cnt = 1;
 
    for (int i = 1; i < n; i++)
    {
        if (arr[i] == arr[i - 1])
            cnt++;
        else
        {
            if (cnt > n / 2)
                return !printf("과반수가 넘는 수 :: %d\n", arr[i - 1]);
            else
                cnt = 1;
        }
 
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

3. O(N)

계수정렬

http://www.crocus.co.kr/470

계수정렬을 이용하여 문제를 해결 할 수 있다.

이때 수가 커진다면 좌표 압축을 통해 수의 범위를 줄여 계수 정렬을 해볼 수 있으나 메모리 공간의 낭비가 심할 수 있다.

과반수의 개념을 이용

어떤 집단에서 과반수라면 그 수는 항상 다른 수들과 상쇄 시켰을 때 1개 이상이 남게 될 것이다.

3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 에서 상쇄를 시켜나가보자.

3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2

2 2 1 1 1 1 2 1 3 2 1 1 1 2

2 2 1 1 1 1 2 1 3 2 1 1 1 2

2 1 1 1 2 1 3 2 1 1 1 2

1 1 2 1 3 2 1 1 1 2

1 1 3 2 1 1 1 2

1 2 1 1 1 2

1 1 1 2

1 1

따라서 우리는 이 과정을 스택을 이용하여 해결한다면 O(N)만에 해결 할 수 있다.

#include <iostream>
#include <cstdio>
#include <stack>
 
using namespace std;
 
int arr[100];
int main()
{
    stack<int> st;
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        int val;
        cin >> val;
 
        if (st.empty())
            st.push(val);
        else
        {
            if (st.top() != val)
                st.pop();
            else
                st.push(val);
        }
 
        arr[i] = val;
    }
    if (st.empty())
        cout << "과반수 이상되는 수가 없습니다. " << endl;
    else
    {
        // 실제 그 수가 과반수인지 한번 더 확인
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (arr[i] == st.top())
                cnt++;
 
        if (cnt > n / 2)
            cout << "과반수 이상인 수 :: " << st.top() << endl;
        else
            cout << "과반수 이상되는 수가 없습니다. " << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>