[백준] #31091 거짓말 - 파이썬

문제

당신 앞에는 $N$명의 사람들이 있다. 각 사람은 자신을 포함하여 몇 명 이상이 거짓말을 하고 있다고 말하거나, 몇 명 이하의 사람이 거짓말을 하고 있다고 말한다.

예를 들어, 각 사람이 다음과 같이 주장한다고 하자.

• 첫 번째 사람이 이렇게 말한다: "1명 이상이 거짓말을 하고 있다!"
• 두 번째와 세 번째 사람이 이렇게 말한다: "1명 이하가 거짓말을 하고 있다!"
• 네 번째 사람이 이렇게 말한다: "2명 이상이 거짓말을 하고 있다!"

이 경우에 가능한 시나리오는 다음과 같다.

• 네 번째 사람만 거짓말을 하고 있다.
• 두 번째와 세 번째 사람이 거짓말을 하고 있다.

사람들의 주장이 주어질 때, 거짓말을 하는 사람의 수로 가능한 것을 모두 구해라.

입력

첫째 줄에 사람의 수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $k_1,\cdots ,k_N$이 공백을 사이에 두고 주어진다.

•  $k_i$가 양의 정수라면, $i$번째 사람이 "$k_i$명 이상이 거짓말을 하고 있다"고 말했다는 뜻이다.
•  $k_i$가 0이거나 음의 정수라면, $i$번째 사람이 "$-k_i$명 이하가 거짓말을 하고 있다"고 말했다는 뜻이다.

출력

첫째 줄에 거짓말을 하는 사람의 수로 가능한 수의 개수를 출력한다.

둘째 줄에 가능한 수들을 공백을 사이에 두고 오름차순으로 출력한다.

제한

•  $1\leq N\leq 500\, 000$ 
•  $-N\le k_i\le N$ ($1\le i\le N$)

예제 입력 1 

4
1 -1 -1 2

예제 출력 1 

2
1 2

예제 입력 2 

1
0

예제 출력 2 

2
0 1

---

복기

1. 처음에는 무슨 말을 하는지 이해도 못했다... 문제를 이해하고도 구현하는것도 너무 어려웠다ㅠㅠ

2. 가장 핵심적인 알고리즘은 "차분 배열" 이라고 한다 (Prefix Sum). 차분배열에 대해서 먼저 정리하고 넘어가자. 

 

차분 배열

상황: 10일 동안의 도서관 책 대여 기록을 관리합니다. 초기에는 모든 날짜에 0권의 책이 대여되어 있습니다.

일 :    1  2  3  4  5  6  7  8  9  10
대여 :  0  0  0  0  0  0  0  0  0  0

다음과 같은 대여 작업이 수행된다.

명령어
2일부터 5일까지 매일 3권씩 대여됩니다.
4일부터 7일까지 매일 2권씩 추가로 대여됩니다.
3일부터 8일까지 매일 1권씩 반납됩니다.

차분 배열 기법 적용
차분 배열에 변화를 적용할 때는
1. 변화가 시작되는 지점에 +변화량
2. 변화가 끝나는 지점 + 1에 -변화량

적용하면 된다.

초기 차분 배열 설정

일 :    1  2  3  4  5  6  7  8  9  10  11
차분 :  0  0  0  0  0  0  0  0  0  0   0

각 작업 적용
a. 2일부터 5일까지 3권씩 대여:

일 :    1  2  3  4  5  6  7  8  9  10  11
차분 :  0  3  0  0  0 -3  0  0  0  0   0

b. 4일부터 7일까지 2권씩 추가 대여:

일 :    1  2  3  4  5  6  7  8  9  10  11
차분 :  0  3  0  2  0 -3  0 -2  0  0   0

c. 3일부터 8일까지 1권씩 반납:

일 :    1  2  3  4  5  6  7  8  9  10  11
차분 :  0  3 -1  2  0 -3  0 -2  1  0   0

누적 합 계산

일 :    1  2  3  4  5  6  7  8  9  10  11
차분 :  0  3 -1  2  0 -3  0 -2  1  0   0
누적 :  0  3  2  4  4  1  1 -1  0  0   0

최종 대여 상태 계산 (초기 상태 + 누적 변화)

일 :    1  2  3  4  5  6  7  8  9  10
최종 :  0  3  2  4  4  1  1  0  0  0

 

3. 누적합으로 계산해서 가능한 거짓말쟁이  숫자를 카운팅한다. 

---

솔루션

N = int(input())
K = list(map(int, input().split()))

#차분 배열 초기화
diff = [0] * (N+2)

# 각 주장에 대해 거짓말쟁이 조건 반영
for k in K:
    if k > 0:
        diff[0] += 1
        diff[k] -= 1
    else:
        k = -k
        if k + 1 <= N:
            diff[k + 1] += 1
            diff[N + 1] -= 1

# 누적합으로 가능한 x 찾기
liars = []
count = 0
for x in range(N + 1):
    count += diff[x]
    if count == x:
        liars.append(x)

# 출력
print(len(liars))
if liars:
    print(" ".join(map(str, liars)))