2024. 6. 1. 21:34ㆍIT/BaekJoon
문제 링크
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을 사용해야되는 점과 시간이 오래 걸리는 점이 특징인 문제였다.
'IT > BaekJoon' 카테고리의 다른 글
[BAEKJOON] 백준 1449: 수리공 항승 (C#) (0) | 2024.06.02 |
---|---|
[BAEKJOON] 백준 1431: 시리얼 번호 (C#) (0) | 2024.06.02 |
[BAEKJOON] 백준 1166: 선물 (C#) (0) | 2024.06.01 |
[BAEKJOON] 백준 1072: 게임 (C#) (0) | 2024.06.01 |
[BAEKJOON] 백준 1063: 킹 (C#) (0) | 2024.06.01 |