문제
각 땅에 배치된 병사의 번호가 주어질 때, 과반수를 차지하는 번호를 출력하라. 과반수가 없으면 "Sminimum"을 출력한다.
입력
첫째 줄에 땅의 수 N, 이후 N줄에 각 땅의 병사 수와 병사 번호가 주어진다.
출력
각 땅에 대해 과반수 번호 또는 "Sminimum"을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 5 1 2 1 2 1 6 1 2 1 2 1 2 1 1 | 1 Sminimum 1 |
풀이
Boyer-Moore 과반수 투표 알고리즘으로 후보를 찾고, 실제 과반수인지 검증한다.
- 각 땅의 병사 배열을 순회하며 후보와 카운트를 관리한다
- 현재 병사가 후보와 같으면 카운트 증가, 다르면 감소하며 0이 되면 후보를 교체한다
- 후보를 찾은 뒤 실제 등장 횟수가 과반을 넘는지 검증한다
- 과반이면 번호를, 아니면 "Sminimum"을 출력한다
핵심 아이디어: Boyer-Moore 투표 알고리즘은 O(N) 시간, O(1) 공간으로 과반수 후보를 찾을 수 있다.
코드
const solution = (input) => {
const N = +input[0];
const result = [];
for (let i = 1; i <= N; i++) {
const arr = input[i].trim().split(" ");
const cnt = +arr[0];
const soldiers = arr.slice(1);
let candidate = soldiers[0];
let count = 1;
for (let j = 1; j < cnt; j++) {
if (count === 0) {
candidate = soldiers[j];
count = 1;
} else if (soldiers[j] === candidate) {
count++;
} else {
count--;
}
}
let total = 0;
for (let j = 0; j < cnt; j++) {
if (soldiers[j] === candidate) total++;
}
result.push(total > cnt / 2 ? candidate : "Sminimum");
}
return result.join("\n");
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));복잡도
- 시간: O(N × M) (N: 땅 수, M: 병사 수)
- 공간: O(1)