[Java] 백준 31091 - 거짓말

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

 

풀이

 

예를들어, N = 5명이고, 각자 다음과 같이 주장하고 있다

[ 1, 4, 3, 5, 2 ]

 

이 상황에서 거짓말한 사람의 수가 3명이 가능한지 확인하고 싶다면

1. 배열을 정렬한다 : [ 1, 4, 3, 5, 2 ] ==> [ 1, 2, 3, 4, 5 ]

2. (사람의 수  −  3보다 최초로 큰 값의 인덱스) = 5 - 3 = 2

3. 2 != 3

∴ 거짓말한 사람이 3명이 될 수 없다.

 

이런 식으로 가능한 거짓말쟁이의 수를 0부터 N까지 돌려보고, 이분탐색(upper bound)로 실제 거짓말한 인원을 확인하고 비교해주면 된다. 다만 음수와 양수는 따로 다른 배열에 저장해서 돌려야하고, 음수 배열에서 이분탐색 돌릴 때 목표값을 음수로 바꿔주는 것만 조심해주면 된다.

 

 

 

코드

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

public class Main {
	public static int upperBoundBinarySearch(ArrayList<Integer> list, int target) {
		int left = 0;
		int right = list.size();

		while (left < right) {
			int mid = (left + right) / 2;
			if (target < list.get(mid)) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return left;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayList<Integer> pos = new ArrayList<>();
		ArrayList<Integer> neg = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			int temp = Integer.parseInt(st.nextToken());
			if (temp > 0) {
				pos.add(temp);
			} else {
				neg.add(temp);
			}
		}

		Collections.sort(pos);
		Collections.sort(neg);

		int answer = 0;
		StringBuilder sb = new StringBuilder();

		for (int lier = 0; lier <= N; lier++) {
			int actualLier = 0;
			actualLier += (neg.size() - upperBoundBinarySearch(neg, -1 * lier));
			actualLier += (pos.size() - upperBoundBinarySearch(pos, lier));

			if (lier == actualLier) {
				answer++;
				sb.append(lier).append(' ');
			}
		}

		System.out.println(answer);
		System.out.println(sb);
		br.close();
	}
}

 

후기

 

개인적으로 골드5보다는 어렵다고 느낀 문제. 여러가지 풀이가 가능한 것 같다. 다들 위와 비슷한 개념으로 누적합을 사용한 것 같고, 투 포인터도 가능하다고 한다.