1270번: 전쟁 - 땅따먹기

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

주어진 집합들에서 각각의 집합의 과반수 이상의 갯수를 가진 숫자가 있으면 해당 숫자를 출력, 아니면 SYJKGW를 출력한다

처음에는 단순히 Map에 숫자의 갯수를 저장한 후, 과반수 이상의 갯수를 가진 숫자를 찾았다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        outer:
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            if (m == 0) {
                sb.append("SYJKGW").append("\n");
                continue;
            }
            int half = m / 2 + 1;
            Map<Long, Integer> map = new HashMap<>();
            for (int j = 0; j < m; j++) {
                long num = Long.parseLong(st.nextToken());
                map.merge(num, 1, Integer::sum);
                if (map.get(num) >= half) {
                    sb.append(num).append("\n");
                    continue outer;
                }
            }
            sb.append("SYJKGW").append("\n");
        }
        br.close();
        System.out.print(sb);
    }
}

 

 

정답이었지만,  4648ms 라는 시간이 소요되었고 최적화 할 방법이 필요함을 느꼈다. 다른 풀이법을 찾아본 결과, 위의 방법처럼 메모리를 계속 재할당받지 않으면서 보다 빠르게 후보를 찾는 방법인 보이어-무어 알고리즘을 적용하였다. 보이어-무어 알고리즘은 한 번 순회하면서 "과반수 후보"를 찾고, 다시 한 번 순회하며 그 후보가 실제 과반수인지 확인하는 알고리즘으로 Hash 연산이나 공간 복잡도 차이로 인해 더욱 빠르다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        long[] soldiers = new long[100001];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            if (m == 0) {
                sb.append("SYJKGW").append("\n");
                continue;
            }
            for (int j = 0; j < m; j++) {
                soldiers[j] = Long.parseLong(st.nextToken());
            }
            long candidate = 0;
            long count = 0;
            for (int j = 0; j < m; j++) {
                if (count == 0) {
                    candidate = soldiers[j];
                    count = 1;
                } else if (candidate == soldiers[j]) {
                    count++;
                } else {
                    count--;
                }
            }
            
            long actualCount = 0;
            for (int j = 0; j < m; j++) {
                if (soldiers[j] == candidate) {
                    actualCount++;
                }
            }
            
            if (actualCount > m / 2.0) {
                sb.append(candidate).append("\n");
            } else {
                sb.append("SYJKGW").append("\n");
            }
        }
        br.close();
        System.out.print(sb);
    }
}

 

차이는 아래와 같다