백준 10815 - 숫자 카드

백준

황태건 2023. 5. 3. 10:06

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

입력의 개수가 많아 map 컨테이너를 사용해 풀었으나
map은 키와 이에 대응하는 값이 있을때 쓰는 컨테이너고

키의 존재 유무만 알아보기 위해서는 set을 사용하면 된다. (사용법은 유사, set이 tree 구조)

이진탐색으로도 풀 수 있다고 하여 이진탐색도 적용해보았다.

시간 초과가 떴는데, 찾아보니 시간 초과의 원인이

함수를 호출할 때 마다 크기가 큰 배열을 그대로 복사하여 전달하기 때문이였다.

따라서 참조연산자를 활용해 배열의 값을 복사하는 대신 원본 배열에 직접 접근하도록 했다.

배운 내용 :

참조연산자의 활용 (배열에 대한 alias를 제공하기 때문에 빠르게 접근 가능)

출력과 입력이 많을 경우

cin.tie(NULL)

cin.sync_with_stdio(false)

적용해 cin과 cout 연산자 만을 이용해 출력하기