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

문제

드디어 전쟁은 전면전이 시작되었고, 서로 땅을 따먹기 시작했다.
현재 여러 지역은 한창 전쟁이 벌어지고 있는 상황인데, 어느 지역은 거의 전쟁이 마무리 단계로 가고 있다.
하지만 당신은 군대를 보낼 때 적군을 혼란시키기 위해서 우리 나라의 군대라는걸 표시하지 않고, 군대의 번호로 표시했다.
어느 땅에서 한 번호의 군대의 병사가 절반을 초과한다면 그 땅은 그 번호의 군대의 지배하에 놓이게 된다.
이때, 각 땅들을 지배한 군대의 번호를 출력하여라. 만약, 아직 전쟁이 한창중인 땅이라면 “SYJKGW”을 쌍 따옴표 없이 출력한다.

입력 조건

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

출력 조건

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

 

---

 

1. 땅의 개수 받아오기

 

2. 땅에 존재하는 병사 받아오기

각 줄의 제일 처음 숫자는 병사 수(t)입니다.
그러니 병사 수만큼 반복문을 돌려줍니다.

중요한 점은 | Nij | <= 2^31 이라는 조건으로 인해 Long 값으로 군대 번호를 받아야 한다는 점입니다. 
그래서 <군대 번호, 개수> 꼴로 Map을 구성했습니다.

int t = Integer.parseInt(st.nextToken());

HashMap<Long, Integer> milMap = new HashMap<>();

for (int j=0; j<t; j++) {
    long mil = Long.parseLong(st.nextToken());

    milMap.put(mil, milMap.getOrDefault(mil, 0) + 1);
}

 

3. 지배 여부 계산하기

지배 여부는 각 병사가 속한 군대가 전체 인원보다 절반 초과기만 하면 됩니다.

그래서 Map의 key값으로 반복문을 돌리고,
해당 Map의 value값(=군대 번호가 몇 개인지)이 절반을 초과하는지 확인했습니다.

double half = (double) t / 2;

long answer = -1;

for (long m : milMap.keySet()) {
    if (milMap.get(m) > half) {
        answer = m;
        break;
    }
}

 

 

---

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());

            HashMap<Long, Integer> milMap = new HashMap<>();

            for (int j=0; j<t; j++) {
                long mil = Long.parseLong(st.nextToken());
                
                milMap.put(mil, milMap.getOrDefault(mil, 0) + 1);
            }

            double half = (double) t / 2;

            long answer = -1;

            for (long m : milMap.keySet()) {
                if (milMap.get(m) > half) {
                    answer = m;
                    break;
                }
            }

            System.out.println(answer == -1 ? "SYJKGW" : answer);
        }
    }
}

 

 

제가 풀이한 코딩테스트는 아래에서도 확인할 수 있습니다.

https://github.com/eonwy/codingTest/tree/main/%EB%B0%B1%EC%A4%80

codingTest/백준 at main · eonwy/codingTest