백준[1270] 전쟁 - 땅따먹기

문제 설명

1. 문제 링크

http://icpc.me/1270

1270번: 전쟁 - 땅따먹기

2. 풀이

map을 이용하여 풀면 된다.

배열을 2^31칸을 만들 수 없으니 map을 이용하여 병사의 수를 카운트하며 가장 많은 병사가 반절이 넘어간다면 그 인덱스 값을 출력해주면 된다.

조금 추하게 시간제한 꽉꽉 채워서 겨우 맞았다. map을 한두번만 접근을 더 호출해도 시간이 터진다. 최대한 덜 접근해서 겨우 맞았다.

3. 코드

#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;
using  ll = long long;

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        map<ll, int> cnt;
        ll ret = 0, idx = -1;
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            ll num; scanf("%lld", &num);
            ll tmp = ++cnt[num];
            if (tmp > ret) {
                idx = num;
                ret = tmp;
            }
        }
        if (ret > n / 2) printf("%lld\n", idx);
        else printf("SYJKGW\n");
    }
}C++