[백준 31091] 거짓말 - JAVA

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

 

애드 혹 문제다.

문제에 대한 이해(명제), 이상/이하 조건 분리, O(N^2)미만의 접근 모두 어려웠다.

 

 

누적합으로 해당 배열을 기록한다.

p[i] : 거짓말을 한 사람이 i명이라고 가정했을 때, 조건( k명 이상이다)을 만족하는 사람의 수

m[i] : 거짓말을 한 사람이 i명이라고 가정했을 때, 조건( k명 이하이다)을 만족하는 사람의 수

 

 

n명 이상이 거짓말을 하고 있다면,  0~n-1명 이상이 거짓말을 하고 있다는 명제도 참이다.

p[n] = p[0~n-1] + p[n]

 

n명 이하가 거짓말을 하고 있다면,  N~n+1명 이하가 거짓말을 하고 있다는 명제도 참이다.

m[n] = m[N~n+1] + m[n]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());

    List<Integer> list = new ArrayList<>();
    int[] p = new int[N + 1];
    int[] m = new int[N + 1];

    StringTokenizer st = new StringTokenizer(br.readLine());

    for (int i = 0; i < N; i++) {
      int e = Integer.parseInt(st.nextToken());

      if (e > 0) {
        p[e]++;
      } else {
        m[-e]++;
      }
    }

    for (int i = 1; i <= N; i++) {
      p[i] += p[i - 1];
    }

    for (int i = N - 1; i >= 0; i--) {
      m[i] += m[i + 1];
    }

// 전체 사람의 수 - 바른말을 한 사람의 수 = 거짓말을 한 사람의 수
    for (int i = 0; i <= N; i++) {
      if (N - p[i] - m[i] == i) {
        list.add(i);
      }
    }

    StringBuilder sb = new StringBuilder(list.size() + "\n");
    list.forEach(e -> sb.append(e).append(" "));
    System.out.println(sb);
  }
}