1920번: 수 찾기
첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
www.acmicpc.net
1. 입력 갯수만큼 배열을 만들어서 넣어준다
2. 정렬한 후 이진탐색으로 원소 유무 확인한다
[Points]
1. 앞서 정렬에 관해서 몇개 풀어봤는데, 이번에는 탐색에 초점을 맞춰보았따
2. 정렬, 탐색 할 필요 없이 애초에 입력가능한 숫자의 최댓값만큼 배열을 만들어놓고, 입력받은 수의 인덱스로 가서 채우는 방식으로 숫자가 있는지
없는지를 검사할 수 있었다. 이것이 더 좋은 방법 같다
[More]
1. 다른분들 중에는 map 이나 set 을 활용해서 푸신 분들이 많았다. 이걸 써서 다시 풀어보자
2. 이진탐색 직접구현하기
3. 걸리는 시간을 확인하는 방법 찾아보기
'PS > BOJ' 카테고리의 다른 글
| [백준] 10816.cpp.py : 숫자 카드 2 (0) | 2020.05.10 |
|---|---|
| [백준] 2164.cpp : 카드2 (0) | 2020.05.10 |
| [백준] 11650.cpp : 좌표 정렬하기 (0) | 2020.05.10 |
| [백준] 10814.cpp : 나이순 정렬 (0) | 2020.05.10 |
| [백준] 1181 : 단어 정렬 (0) | 2020.05.10 |