[BOJ] 1920 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

문제 : 

• N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력 : 

• 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

 

출력 : 

• M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력 :

5
4 1 5 2 3
5
1 3 7 9 5

 

예제 출력 : 

1
1
0
0
1

 

풀이

1. 예제를 무시하고 문제/입력/출력 에 맞추어 구현한 경우

# N에 입력된 숫자에 맞추어 N개의 정수를 A에 입력
N = int(input())
A =  []
for i in range(0, N):
    num = random.randint(-2^31,(2^31)-1)
    A.append(num)

# M에 입력된 숫자에 맞추어 M개의 정수를 B에 입력
M = int(input())
B = []
for i in range(0, M):
    num2 = random.randint(-2^31,(2^31)-1)
    B.append(num2)

# B 내에 있는 변수가 A에 포함된 경우에는 1, 아닌 경우에는 0을 출력
final_list = [1 if x in A else 0 for x in B]
for x in final_list:
    print(x)

 

2. 예제에 맞추어 구현 (1)

# 속도를 비교해본 결과
# 1) map → set
# 2) map → list (시간초과)
# 3) list로 바로 처리 (시간초과)


N = int(input())
# A = [int(x) for x in input().split()]
# A =  list(map(int, input().split()))
A =  set(map(int, input().split()))

M = int(input())
# B = [int(x) for x in input().split()]
B =  list(map(int, input().split()))

for num in B:
    if num in A:
        print(1)
    else:
        print(0)

문제 출제의 의도는 이진 탐색을 쓰는 것이지만 이에 대해 몰랐기에

입력된 숫자를 처리하는 과정에서 속도 저하가 발생하였다고 판단하고 수정하였다.

(이진 탐색보다 상기 방법이 더 빠르고 코드도 간단하다)

 

3. 예제에 맞추어 구현 (2) - 이진 탐색

def binary_search(A, num):
    A_min = 0
    A_max = len(A) - 1

    while A_min <= A_max:
        A_target = (A_min + A_max) // 2
        if A[A_target] == num:
            return True
        elif A[A_target] < num:
            A_min = A_target + 1
        elif A[A_target] > num:
            A_max = A_target - 1
    return False


N = int(input())
A = list(map(int, input().split()))
A.sort()  # 이진 탐색을 사용하려면 리스트를 정렬해줘야함.

M = int(input())
B = list(map(int, input().split()))

for num in B:
    if binary_search(A, num):
        print(1)
    else:
        print(0)

 

이진 탐색 방법 :

• 정렬된 리스트이 가운데 값 선택
• 선택한 값과 찾고자 하는 값 비교
• 선택한 값 = 찾고자 하는 값 : return True
• 선택한 값 < 찾고자 하는 값 : 리스트의 오른쪽 절반에서 계속 검색
• 선택한 값 > 찾고자 하는 값 : 리스트의 왼쪽 절반에서 계속 탐색
• 끝까지 없는 경우 : return False