아이디어

• 거짓말 한 사람이 $k$명일 때를 생각해보자.
• 이때, "거짓말한 사람이 "$0$명 이하", "$1$명 이하", "$2$명 이하", ..., "$k-1$명 이하"라 한 사람들과 "$k+1$명 이상", "$k+2$명 이상", ..., "$N$명 이상"이라고 한 사람이 거짓말한 사람이어야 하고, 그 수가 정확히 $k$명이어야 한다.
  • 즉, "거짓말한 사람이 $x$명 이하"라고 한 사람의 수를 L[x], "거짓말한 사람이 $x$명 이상"라고 한 사람의 수를 U[x]라 하면 L[0] + ... + L[k-1] + U[k+1] + ... + U[N]을 구하면 된다.
• $N \le 500\ 000$이므로, 매번 위 식을 구하고 있으면 시간 초과가 날 것이다. 누적합을 이용해 $O(N)$에 풀 수 있도록 한다.
  • 점화식은 코드 참조

코드 (Python)

import sys
input=sys.stdin.readline

N=int(input())

L=[0]*(N+1)
U=[0]*(N+1)
for x in map(int,input().split()):
    if x > 0:
        U[x] += 1
    else:
        L[-x] += 1

LS=[0]*(N+1)
US=[0]*(N+1)

LS[0] = 0
for i in range(1, N+1):
    LS[i] = LS[i-1] + L[i-1]
US[N] = 0
for i in range(N-1, -1, -1):
    US[i] = US[i+1] + U[i+1]

ans = []
for i in range(N+1):
    if US[i] + LS[i] == i:
        ans.append(i)
print(len(ans))
print(*ans)

메모리 및 시간

• 메모리: 210204 KB
• 시간: 356 ms

리뷰

• 'Goodbye BOJ, 2023!' 대회 B번 문제
• 2솔 중에 한 문제로 풀었다는 것에 의의를 두자.
• 내년에 더 많이 풀 수 있기를...