[파이썬/Python] 백준 1920번: 수 찾기

숨·2024년 7월 6일

코테

알고리즘 문제 풀이

목록 보기

16/105

📌 문제 : 백준 1920번

📌 문제 탐색하기

N : 정수의 수 (1 ≤ N ≤ 100,000)
A : N개의 정수를 저장한 리스트
M : 찾고자 하는 정수의 수 (1 ≤ M ≤ 100,000)

✅ 입력 조건
1. N 입력
2. N개의 정수 입력
3. 찾으려는 정수의 수 M 입력
4. M개의 정수 입력
✅ 출력 조건
1. M개의 정수가 N개의 정수 중에 있는지 여부를 한줄에 하나씩 출력
2. 존재하면 1, 존재하지 않으면 0 출력

M개의 정수를 찾아내기 위해 이분 탐색을 활용한다.

N개의 정수를 입력받아 A라는 리스트에 저장하고 오름차순 정렬한다.
입력받은 M개의 정수를 target이라는 리스트에 저장한다.

for문을 통해 M개의 정수를 돌면서 하나씩 이분탐색을 적용한다.
start와 end를 정의하고 while문을 작성한다.

target을 찾았는지 여부를 저장하는 변수를 정의한다.

start와 end의 가운데 수인 mid를 정의하여, A 리스트에서 해당 mid 인덱스의 값이 target과 동일한지 확인한다.
target과 비교하는 과정을 start가 end보다 작다는 조건 내에서 반복한다.

target과 비교하는 과정
A는 오름차순 정렬되어 있기 때문에,
1. mid 값이 target보다 작다 → mid 위치보다 큰 쪽에서 원하는 target이 있을 것이라 기대할 수 있다.
2. mid 값이 target보다 크다 → mid 위치보다 작은 쪽에서 원하는 target이 있을 것이라 기대할 수 있다.

while문이 종료된 후, target 존재 여부 변수 값을 확인한다.
존재하면 1, 이분탐색이 끝나도 찾지 못했다면 0이 저장되어 있을 것이므로 그 값을 출력하면 된다.

가능한 시간복잡도

입력받아 리스트 만들기 → $O(N)$ , $O(M)$
for 루프에서 연산하기 → $O(M)$
while 루프에서 이분 탐색하기 → $O(logN)$

최종 시간복잡도
$O(MlogN)$ 으로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

for 루프 내 while 루프에서 이분탐색을 통해 해당 수가 존재하는지 확인한다.

📌 코드 설계하기

N 입력
N개의 정수 입력받아 A에 저장
A 오름차순 정렬
M 입력
M개의 정수 입력받아 target에 저장
이분 탐색

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. N 입력
N = int(input())

# 2. N개의 정수 입력받아 A에 저장
A = list(map(int, input().split()))

# 3. A 오름차순 정렬
A.sort()

# 4. M 입력
M = int(input())

# 5. M개의 정수 입력받아 target에 저장
target_list = list(map(int, input().split()))

# 6. 이분 탐색
for i in range(M):
    target = target_list[i]

    start = 0
    end = N - 1

    is_exist = 0

    while start <= end:
        mid_idx = (start + end) // 2
        mid_val = A[mid_idx]

        #  mid 값보다 큰 곳에서 target 찾아야 함
        if mid_val < target:
            start = mid_idx + 1
        # mid 값보다 작은 곳에서 target 찾아야 함
        elif mid_val > target:
            end = mid_idx - 1
        # target 찾음
        else:
            is_exist = 1
            break

    # 7. 원하는 답 출력
    print(is_exist)

결과

다른 풀이

import sys 

N = int(input())

# 탐색 시간 줄이기 위해 set으로 받음
n_list = set(map(int, input().split()))

M = int(input())

target_list = list(map(int, input().split()))

# target_list 각 원소별 탐색
for target in target_list:   
	print(1) if target in n_list else print(0)