[백준] 15719번 - 중복된 숫자 (C++)

15719번: 중복된 숫자

 

문제

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을 출력하라.

 

 

풀이과정

들어오는 입력값의 범위가 10,000,000까지로 상당히 넓은 범위를 가지고 있어서 시간초과 및 메모리초과를 신경써줘야하는 문제였었다.

map을 사용해서 구현하거나 int배열을 사용해서 구현을 했었는데 시간초과가 발생이 되어 bool형태의 배열을 사용하였다.

 

code

#include <iostream>

bool	arr[10000001];

int	main(void)
{
	std::ios_base :: sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL);

	int n, temp;

	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> temp;
		if (!arr[temp]) arr[temp] = true;
		else {
			std::cout << temp << "\n";
			return (0);
		}
	}
	return (0);
}

 

후기

int배열과 bool 배열이 서로 시간복잡도에서 차이가 생긴다는 것을 처음 알게되었다.

둘 다 사용가능한 문제라면 bool 형태의 배열 사용하기.