8001 : 빠진 숫자 찾기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 16
•통과: 14
•만든사람: suakii
문제 설명
$1$부터 $N$까지의 정수가 있습니다. 그 중 정확히 하나의 수가 빠진 $N-1$개의 정수가 주어질 때, 빠진 숫자를 찾는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 2 \times 10^5$
• 주어지는 $N-1$개의 정수는 모두 $1$ 이상 $N$ 이하이며 서로 다릅니다.
[제약 조건]
• $2 \le N \le 2 \times 10^5$
• 주어지는 $N-1$개의 정수는 모두 $1$ 이상 $N$ 이하이며 서로 다릅니다.
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
둘째 줄에 $N-1$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N-1$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
빠진 정수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
2 3 1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
$1$부터 $N$까지의 총합 공식 $\frac{N(N+1)}{2}$을 구한 뒤, 입력된 $N-1$개 원소들의 합을 빼면 $O(N)$ 시간 및 $O(1)$ 추가 메모리로 빠르게 빠진 숫자를 구할 수 있습니다.