-
1920. [Python]수 찾기Python_알고리즘/Silver IV 2023. 4. 12. 11:50
1. 문제
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
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 이분 탐색
3. 파이썬 코드
import sys input = sys.stdin.readline N = int(input()) N_list = list(map(int,input().split())) M = int(input()) M_list = list(map(int,input().split())) # 이분 탐색을 위한 정렬 N_list.sort() # 리스트 값들 반복문 처리 for i in M_list: # 시작은 0번 끝은 N-1 중간은 N//2 start = 0 end = N-1 mid = N//2 # 만약 i 값이 범위를 벗어난 경우 0 출력 if i > N_list[-1] or i < N_list[0]: print(0) # 0번 인덱스 끝 인덱스 중간 인덱스값이랑 같은경우 1출력 elif N_list[start] == i: print(1) elif N_list[end] == i: print(1) elif N_list[mid] == i: print(1) # 그 외의 경우 else: # 시작값과 끝값이 같으면 계속 반복하기 때문에 그 전까지 while start != end: # 만약 mid 값이랑 같은 경우 출력 if i == N_list[mid]: print(1) break # 그 외의 경우 mid 값보다 작은 경우 elif i < N_list[mid]: # end 자리에 mid 삽입 후 mid 값 조정 end = mid mid = (start+end)//2 # mid 값보다 큰 경우 else: # 시작값을 mid +1 로 변경 start = mid+1 mid = (start+end)//2 # break에 의한 종료가 아닌경우 else: # start 랑 end 값이 동일하므로 start 인덱스 값과 같은 경우 1 출력 그 외의 경우 0 if N_list[start] == i: print(1) else: print(0)
4. 문제를 풀고난 후 생각
- 이분 탐색을 진행하기 위해서 조건을 먼저 생각해봤다. 정렬된 리스트를 가지고 탐색을 진행해야 하므로 정렬을 먼저 진행해 주었다.
- 이후 이분탐색을 하기위해서 반복문의 조건을 설정하는데 있어서 제일 처음 start 값을 갱신해주는 것을 mid 값으로 넣어줘서 무한루프가 돌았다. ( start = mid + 1 이 start = mid 로 되어있었다. )
- 제일 처음 시작했을때 start, mid, end 인덱스 값을 체크하는 것으로 불필요한 반복문을 안돌아도 될 수 있어서 추가해 줬다.
- while에서 break 가 아닌 조건에 의하여 끝났을 경우 else 문으로 값을 출력했다.
5. 문제를 푸는데 도움이 되는 지식
- 이분 탐색
- 정렬
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1639. [Python]행운의 티켓 (0) 2023.04.17 1337. [Python]올바른 배열 (0) 2023.04.13 1755. [Python]숫자놀이 (0) 2023.04.11 1120. [Python]문자열 (0) 2023.04.09 1235. [Python]학생 번호 (0) 2023.04.01