[BAEKJOON] 백준 1270: 전쟁 - 땅따먹기 (C#)

문제 링크

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

 

 

문제

드디어 전쟁은 전면전이 시작되었고, 서로 땅을 따먹기 시작했다.

현재 여러 지역은 한창 전쟁이 벌어지고 있는 상황인데, 어느 지역은 거의 전쟁이 마무리 단계로 가고 있다.

하지만 당신은 군대를 보낼 때 적군을 혼란시키기 위해서 우리 나라의 군대라는걸 표시하지 않고, 군대의 번호로 표시했다.

어느 땅에서 한 번호의 군대의 병사가 절반을 초과한다면 그 땅은 그 번호의 군대의 지배하에 놓이게 된다.

이때, 각 땅들을 지배한 군대의 번호를 출력하여라. 만약, 아직 전쟁이 한창중인 땅이라면 “SYJKGW”을 쌍 따옴표 없이 출력한다.

 

 

입력

첫째 줄에는 땅의 개수 n(n<=200)이 주어진다. 그리고 두 번째 줄에서 n+1번째 줄에는 제일 처음에 숫자 Ti(i번째 땅의 병사수, Ti<=100,000)와, Ti개의 숫자 (각각 병사의 군대 번호)가 주어진다. i번째 땅의 j번째 병사 번호 Nij가 주어진다. ( | Nij | <= 2^31 )

 

 

출력

첫째 줄에는 각각의 땅의 상태를 순서대로 출력한다. 만약 땅이 지배가 되어있다면 그 지배한 병사의 번호를 출력하고, 아니라면 “SYJKGW”을 쌍 따옴표 없이 출력한다.

 

 

 

통과한 답안

namespace _1270
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            for (int i = 0; i < n; i++)
            {
                string[] inputs = Console.ReadLine().TrimEnd().Split(' ');
                Dictionary<long, int> condition = new Dictionary<long, int>();

                for (int j = 1; j < inputs.Length; j++)
                {
                    long army = long.Parse(inputs[j]);

                    if (condition.ContainsKey(army))
                    {
                        condition[army]++;
                    }
                    else
                    {
                        condition.Add(army, 1);
                    }
                }

                long conditionLen = condition.Select(x => x.Value).Sum();
                bool IsOccupy = false;
                long occupyArmy = 0;

                foreach (var item in condition)
                {
                    if (item.Value > conditionLen / 2)
                    {
                        IsOccupy = true;
                        occupyArmy = item.Key;
                        break;
                    }
                }

                Console.WriteLine(IsOccupy ? occupyArmy : "SYJKGW");
            }
        }
    }
}

 

땅의 개수, 각 땅에 존재하는 병사의 수와 병사가 속한 군대의 번호가 주어질 때,

만약 특정 군대의 번호에 속하는 병사의 수가

그 땅에 존재하는 병사의 수의 절반을 초과하는 경우에

그 군대의 번호를 출력하고, 그렇지 않으면 " SYJKGW"를 출력하는 문제이다.

 

아래와 같이 Dictionary를 이용하여 해당 땅에 존재하는 군대별 병사의 수를 저장한다.

Dictionary<long, int> condition = new Dictionary<long, int>();

for (int j = 1; j < inputs.Length; j++)
{
    long army = long.Parse(inputs[j]);

    if (condition.ContainsKey(army))
    {
        condition[army]++;
    }
    else
    {
        condition.Add(army, 1);
    }
}

 

그 후에 그 땅에 존재하는 총 병사의 수를 conditionLen으로 저장한 후에

각 군대의 병사 수를 이용하여 절반을 초과하는 군대가 있다면

bool 값을 true로 변경하고 지배한 군대의 번호를 저장한다.

long conditionLen = condition.Select(x => x.Value).Sum();
bool IsOccupy = false;
long occupyArmy = 0;

foreach (var item in condition)
{
    if (item.Value > conditionLen / 2)
    {
        IsOccupy = true;
        occupyArmy = item.Key;
        break;
    }
}

 

이후의 아래의 코드를 이용하여 지배하는 군대가 있다면 그 군대의 번호를,

지배하는 군대가 없다면 "SYJKGW"를 출력하도록 구현하였다.

Console.WriteLine(IsOccupy ? occupyArmy : "SYJKGW");

 

 

이 문제를 푸는 과정에서 땅의 개수 n 값도 최대 200이고

병사의 수가 100,000이하, 군대 번호의 절댓값이 2^31(int범위) 이므로

매우 큰 값을 이용하게 되므로 long을 사용해야되는 점과 시간이 오래 걸리는 점이 특징인 문제였다.