거짓말하는 사람 수 알아내는 방법(놀라운 양방향 누적합 테크닉)

1. 문제

 

31091번: 거짓말 (acmicpc.net)

31091번: 거짓말

 

 

2. 풀이

 

K명이 거짓말 한다고 가정하자.

 

K = 0,1,2,3,..,n이다.

 

각각의 경우에 대하여 실제로 각 사람들의 말과 비교할때 누가 거짓말을 하는지 알 수 있다.

 

이때, 정말로 거짓말하는 사람 수가 K명으로 일치한다면 그러한 K값은 정답에 포함될 것이다.

 

예를 들어 2명이 거짓말을 한다고 하면...

 

"1명 이상이 거짓말하고 있다."는 참이다. 실제로 2명이 거짓말하고 있으니까

 

"1명 이하가 거짓말하고 있다."는 거짓이다. 

 

"2명 이상이 거짓말하고 있다."는 참이다.

 

"3명 이상이 거짓말하고 있다."는 거짓이다.

 

만약 K명이 거짓말하고 있다면,  X = K+1,K+2,...,n에 대하여 "X명 이상이 거짓말하고 있다."는 모두 거짓이다.

 

반대로, X = K-1,K-2,K-3,..0에 대하여 "X명 이하가 거짓말하고 있다."는 모두 거짓이다.

 

 

만약 각 인덱스 0,1,2,3,..,n에 대하여 배열 S가 S[i] = i명이 거짓말한다고 가정할때, 실제 거짓말하는 사람 수

 

라고 정의한다면..?

 

배열 A[i] = k라는 것은 "k명 이상이 거짓말하고 있다."는 말인데, 

 

0명,1명,2명,...,k-1명이 거짓말하고 있다고 가정하면 "k명 이상이 거짓말하고 있다"는 거짓말이다.

 

따라서 S[0] += 1, S[1] += 1, S[2] += 1,.., S[k-1] += 1을 해줘야한다.

 

그런데 배열 A의 크기 n이 50만이라 0~k-1까지 모두 +1을 항상 해주면 $O(N^{2})$이라 시간초과난다

 

여기서 S[k-1]에만 +1을 해준다면?

 

배열 A의 모든 원소를 순회하면서 A[i] = k > 0일때, S[k-1]에만 +1을 표시해두고,

 

다시 S배열을 순회해서 n-1에서 0 방향으로 누적합을 해준다면?

 

모든 A의 원소에 대하여 S[0] += 1, S[1] += 1, S[2] += 1,.., S[k-1] += 1에 모두 해주는 효과와 동일해진다.

 

O(N)에 거짓말하는 사람 수를 모두 표시할 수 있다

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

반대로 배열 A[i] = -k라는 것은 "k명 이하가 거짓말하고 있다."는 말이다.

 

이 말은 k+1, k+2, ... ,n명이 거짓말하고 있다고 가정할때 거짓말이다.

 

따라서 S[k+1] += 1, S[k+2] += 1, ... ,S[n] += 1에 모두 표시해줘야한다.

 

하지만 n이 최대 50만이라 최악의 경우 $O(N^{2})$이므로 매번 k+1~n을 모두 표시하면 시간초과날 것이다.

 

그래서 이번엔 A[i] = -k일때, S[k+1]에만 +1을 표시해준다.

 

배열 A의 모든 원소를 순회하고 다시 S배열을 순회해서 0에서 n-1방향으로 누적합을 해준다면?

 

A의 모든 원소에 대하여 S[k+1] += 1, S[k+2] += 1, ... ,S[n] += 1에 모두 표시해주는 효과와 동일해진다.

 

역시 O(N)에 거짓말하는 사람 수를 표시해줄 수 있다.

 

따라서 두 경우를 모두 합쳐주면 O(N)에 K = 0,1,2,..,n명이 거짓말하고 있을때 실제로 거짓말하는 사람 수를 찾을 수 있다.

 

이렇게 구한 배열에서 i명이 거짓말하고 있다고 가정할 때 실제로 거짓말하는 사람 수 S[i]가 i인 경우만 찾으면 된다

 

n = int(input())

A = list(map(int,input().split()))

#si = i명이 거짓말한다고 했을때, 거짓말하는 사람의 수

s1 = [0]*(n+1) #우측으로 누적
s2 = [0]*(n+1) #좌측으로 누적

#A[i] = k, k명 이상이 거짓말하고 있다
#거짓말하는 사람이 k-1,k-2,k-3,..일때 거짓말하는 사람
#A[i] = -k, k명 이하가 거짓말하고 있다
#거짓말하는 사람이 k+1,k+2,.k+3,..일때 거짓말하는 사람
for i in range(n):
    
    if A[i] > 0 and A[i] <= n:
        
        s2[A[i]-1] += 1
    
    elif A[i] <= 0 and A[i] > -n:
        
        s1[-A[i]+1] += 1

#k+1에 표시한 경우, 0에서 n-1방향으로 누적합해주면
#k+1,k+2,k+3,..,n에 모두 +1을 해준 효과
for i in range(1,n+1):
    
    s1[i] += s1[i-1] 

#k-1에 표시한 경우, n-1에서 0방향으로 누적합해주면
#k-1,k-2,...,0에 모두 +1을 해준 효과
for i in range(n-1,-1,-1):
    
    s2[i] += s2[i+1]

count = 0
answer = []

#i명이 거짓말한다고 할때, 실제 거짓말하는 사람 수 s1[i]+s2[i]가 i인 경우만 정답
for i in range(n+1):
    
    if (s1[i]+s2[i]) == i:
        
        answer.append(i)
        count += 1        

print(count)
print(*answer)