BOJ 백준온라인져지 15719 중복된 숫자 풀이

문제 설명

중복된 수를 구하면 된다.

풀이

1. Bitset 을 사용하는 방법

bitset 은 bit 의 0 1 로 그 숫자가 있나 없나 확인하는 테크닉이다.

나중에 직접 구현해보면서 자세하게 적겠다.

2. 등차수열의 합을 이용하는 방법

S = N(N - 1)/2 + M

M = S - N(N - 1)/2

ISKU 님의 Buffer read 부분을 참고했습니다.

해답

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/15719
	* BOJ 백준온라인져지 15719 중복된 숫자 풀이
	*/
	public class Main {
	private static byte[] buffer = new byte[78888905];
	private static int next;
	private static int b;
	public static void main(String args[]) throws IOException {
	System.in.read(buffer, 0, buffer.length);
	long N = nextInt();
	long sum = 0;
	for (int i = 0; i < N; i++) {
	sum += nextInt();
	}
	// sum - n(n - 1) / 2 = m
	System.out.println(sum - (N * (N - 1) / 2));
	}
	private static long nextInt() {
	long n = buffer[next++] - '0';
	while ((b = buffer[next++]) >= '0')
	n = (n * 10) + (b - '0');
	return n;
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

1부터 N - 1까지의 정수가 하나씩 정렬되지 않은 채로 저장되어 있는 어떤 수열 A가 있다. 수열 A에 임의의 정수 M(1 ≤ M ≤ N – 1)을 넣어 크기가 N인 수열로 만들었을 때, 임의의 정수 M을 찾는 프로그램을 작성하라.

입력

첫째줄에 수열의 크기 N(2 ≤ N ≤ 10,000,000)이 주어진다.

둘째줄에 수열 A의 원소인 N개의 정수가 주어진다. 입력으로 주어지는 정수는 모두 1부터 N – 1 사이의 정수이며 문제의 답인 M을 제외하고는 모두 서로 다른 정수이다.

출력

M을 출력하라.

예제 입력 1 

10
1 2 2 5 6 4 3 7 8 9

예제 출력 1 

2

출처

University > 중앙대학교 > CodeRace 2018 1번