1270번 : 전쟁 - 땅따먹기

https://www.acmicpc.net/problem/1270

1270번: 전쟁 - 땅따먹기

 

일일 실버 문제를 풀다가 발견한 문제이다. 시간 제한이 10초라 자료구조에 테스트케이스마다 모든 값들을 집어넣고 과반수인지 확인해주는 방법으로 구현하였다. 자료형을 long long으로 확인하는걸 잊지말자.

 

 

태그를 보니 처음보는 알고리즘이 들어가있었다.

 

보이어-무어 다수결 투표

 

해당하는 문제는 백준안에 단 3개만 존재하였고 검색을 조금해보았다. 요약해보면 다음과 같다. 

- N명의 후보들 중에서 투표를 진행하였을때 과반수 이상의 후보가 될 수 있는 후보를 알아내는 알고리즘이다.

즉, 해당 알고리즘을 통해 과반수 이상의 투표를 받았음을 확정 지을 수는 없다.

 

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

Boyer–Moore majority vote algorithm - Wikipedia

증명이 궁금하다면 잘 설명되어있는 위키피디아를 읽어보자고 하자. 로직자체는 정말 간단하다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 200000000;
const double pi = 3.14159265358979;
const ll MOD = 987654321;

void yesno(bool a)
{
	if (a)
		cout << "Yes\n";
	else
		cout << "No\n";
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int T;

	cin >> T;

	while (T--)
	{
		int n;
		cin >> n;

		vector<ll> v;

		ll count = 0;
		ll major = 0;

		rep(i, n)
		{
			ll tmp;
			cin >> tmp;
			v.push_back(tmp);

			if (count == 0)
				major = tmp;

			if (major == tmp)
				count++;
			else
				count--;
		}

		ll cnt = 0;
		rep(i, n)
		{
			if (major == v[i])
				cnt++;
		}

		if (cnt <= n/2)
			cout << "SYJKGW\n";
		else
			cout << major << '\n';
	}

	return 0;
}

 

count와 major 부분에서

count는 과반수 원소를 판단하는 값

major에는 과반수의 후보가 될수 있는 값

이 저장되고 이후에 과반수 이상인지 확인한다.

 

 

해당 알고리즘을 사용했을때 시간복잡도가 절반으로 줄었음을 볼수있다.