[백준 01270] 전쟁 - 땅따먹기 [Java]

문제

1270번: 전쟁 - 땅따먹기

1270번: 전쟁 - 땅따먹기

 

---

풀이

병사들의 번호가 주어질 때, 과반수를 넘는 병사가 존재하는지 검사하는 문제다.

Boyer-Moore Voting으로 과반수가 넘는 병사를 빠르게 찾는 방법으로 풀이했다.

병사의 번호가 int 범위보다 크므로 long을 사용하자.

            long candidate  = -1, virtualCnt = 0;
            for (int i = 0; i < N; ++i) {
                // Solve
                A[i] = Long.parseLong(st.nextToken());

                if (virtualCnt == 0) {
                    candidate  = A[i];
                    virtualCnt = 1;
                } else if (A[i] == candidate) {
                    ++virtualCnt;
                } else {
                    --virtualCnt;
                }
            }

가상의 병사 번호 빈도가 실제로 절반을 초과하는지 검사 후 병사의 번호 또는 “SYJKGW”을 출력하자.

            long actualCnt = 0;
            for (long a : A) {
                if (a == candidate) ++actualCnt;
            }
            sb.append(actualCnt > N / 2 ? candidate : "SYJKGW").append("\\n");
        }

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/01270.java

problem-solving/baekjoon-online-judge/easy/01270.java at main · rogi-rogi/problem-solving