반응형
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
소스코드
- 자료형
- 이분탐색
풀이
★ 이번 문제는 자료형을 사용하거나 이분탐색을 사용하는 방식으로 해결할 수 있는 문제입니다. 먼저 자료형 set을 사용하면 입력받은 a리스트에서 중복된 수가 제거되고 값들을 정렬한 형태로 반환합니다. b 리스트를 돌면서 in을 활용하여, 해당 수가 a에 들어있다면 1을, 없다면 0을 출력합니다.
★ 이분탐색을 위해 리스트 a를 정렬해줍니다. 인덱스를 사용하여 mid 값을 찾아나갈 것이기에 시작점과 끝점을 a리스트의 처음과 끝인 0, n-1로 설정합니다.
★ lt <= rt 동안 반복하면서 x가 a[mid]와 같을 때 1을 출력하고 while문을 break 해준 뒤 다음 수로 넘어갑니다. 만약 x가 a[mid]보다 크다면 a[mid]보다 작은 값들은 x가 될 수 없기 때문에 lt를 mid+1해주고, a[mid]가 x보다 크다면 반대로 rt를 mid-1해줍니다.
★ while ~ else ~ 문을 사용하여 while문에서 break에 걸리지 않고 정상적으로 while문이 끝난다면 x가 a리스트에 없다는 것이기에 0을 출력해줍니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 2470번: 두 용액 (Python) (0) | 2023.06.06 |
|---|---|
| [백준 알고리즘] 10815번: 숫자카드 (Python) (0) | 2023.06.05 |
| [백준 알고리즘] 2812번: 크게 만들기 (Python) (0) | 2023.06.03 |
| [백준 알고리즘] 3986번: 좋은 단어 (Python) (0) | 2023.06.03 |
| [백준 알고리즘] 17608번: 막대기 (Python) (0) | 2023.06.03 |