200916 숫자 카드 10815번(C++)-해결

www.acmicpc.net/problem/10815

10815번: 숫자 카드

문제:

카드에 적힌 수들을 A, B로 나타냈을 때 A와 B는 입력 받는 개수(n,m)도 다르다.

나중에 입력 받은 B에서 처음에 입력 받은 A에 있는 숫자면 1 없으면 0을 출력한다.

 

github.com/decten/AlgorithmStudy/blob/master/%EC%88%AB%EC%9E%90%EC%B9%B4%EB%93%9C.cpp

코드:

C++에서는 binary_search()로 이진(이분) 탐색을 하는 함수를 제공 합니다. 단 사용하려면 배열이 정렬 된 상태여야 합니다. binary_search 함수의 사용법은 binary_search(처음 주소, 끝 주소, 찾고 싶은 값) 입니다. 반환 값은 찾는 값의 유무에 따라 true, false를 반환합니다.

인덱스를 받고 싶을 때는 lower_bound, upper_bound 함수를 사용합니다.

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

벡터 보다는 일반 배열의 인덱스 접근이 더 빠릅니다. 

문제에 나오는 수인 500000 크기의 배열을 선언하면 프로그램이 에러가 뜨면서 실행이 안 됩니다.

이때 해결 방법으로 2가지 방법을 생각했고, 저는 벡터를 사용했습니다.

1. 전역 변수로 선언 해서 힙 할당

2. vector 사용

시간초과가 떠서 cstdio 헤더 파일을 사용하고, cin과 cout을 scanf와 printf로 변경 했더니 통과 했습니다.