백준 - 1920. 수 찾기(MJ)

#1920. 수 찾기

백준의 실버4티어 문제이다.

📖Problems

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

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

예제 입력 1

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

예제 출력 1

1
1
0
0
1

🔍Approach

🚩My submission : Try1 - Bruete Force

1. n과 n개의 정수를 담는 origin 리스트, m과 m개의 정수를 담는 compare리스트를 입력받는다.
2. 이중 for문을 이용해 compare과 origin에 있는 값을 각각 비교한다.
   1. compare리스트에 있는 값이 origin에 있으면 tag를 True로 바꾸고, 그게 아니라면 False를 저장한다.
3. tag가 True라면 1을 출력하고 아니라면 0을 출력한다.

n = int(input())
origin = [int(n) for n in input().split()]
m = int(input())
compare = [int(m) for m in input().split()]
tag = True
for i in compare:
    for j in origin:
        if i==j:
            tag = True
            break
        else:
            tag = False
    if tag == True:
        print(1)
    else:
        print(0)

결과 : 시간초과

시간 초과 나올 줄 알았다. 브루트포스밖에 풀이가 생각나지 않았다. 그러면 이중 for문을 사용해야 하기 때문에 시간초과가 날 수 밖에 없었다.

이 문제는 이진탐색 유형이었기 때문에 이 유형에 대해 알아보았다.

🧐이진탐색

데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘

• 배열의 중간에 있는 임의의 값을 선택해 찾고자 하는 값 x와 비교한다.
• x가 중간값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.
• 동일한 방법으로 다시 중간의 값과 임의로 선택해 비교한다.
• 해당 값을 찾을 때까지 반복한다.

구현

인덱스를 이용한다. 인덱스의 최소, 최대 값을 따로 저장해 탐색이 진행될 때마다 갱신하고 탐색하는 배열의 범위를 줄여나간다.

구현방법은 2가지가 존재한다.

1. 반복문 이용

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

1. 재귀함수 이용

int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}

참고 사이트 : **이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

🚩My submission : Try2 - Binary Search

**이를 통해 다시 코드를 수정해보았다.**

FLOW

1. n과 n개의 정수를 담는 origin 리스트, m과 m개의 정수를 담는 compare리스트를 입력받는다.
2. 이진탐색을 위해 low와 high을 두고 탐색할 것이기 때문에 origin리스트를 정렬한다.
3. target값은 compare에 각 인덱스에 해당하는 값이므로 for문이 필요하다. 매번 시작할 때마다 low와 high값을 초기값인 0과 마지막 인덱스값으로 초기화시켜준다.
4. mid의 값은 low와 high의 값에 따라 달라진다. 따라서 while반복문 안에 그 값을 설정해준다. mid에 해당하는 origin값과 target값과 비교한다.
   1. 이때 같다면, tag는 True로 설정하고 1을 프린트하고 반복을 종료한다.
   2. target 값이 더 작다면, mid 기준으로 오른쪽은 볼 필요가 없다. 따라서 high값을 mid - 1로 설정해준다.
   3. target 값이 더 크다면, mid 기준으로 왼쪽은 볼 필요가 없다. 따라서 low 값을 mid + 1로 설정한다.
5. 이를 low가 high의 값보다 같거나 작을 때까지 반복한다.
   • 이때 while의 범위는 low < high이 아니라 low≤high이어야 한다.
     • compare리스트에서 마지막 인자인 ‘5’의 경우, orgin.sort()하면 맨 마지막인 5에 해당하기 때문이다. 또한 origin의 인덱스는 0~4까지이기 때문에 마지막까지 봐주어야 하기 때문이다.
     • 작동 과정을 살펴보면
     • target = 5
       • low = 0, high = 4, mid = 2, origin[mid] = 3, target값이 더 크므로, low = mid + 1 = low = 3
       • low = 3, high = 4, mid = 3, origin[mid] = 4, target 값이 더 크므로, low = mid + 1 = low 4
       • low = 4, high = 4, mid = 4, origin[mid] = 5, target값과 같으므로 print(1)
6. 이후 for문을 통해 그 다음 인덱스값이 위의 반복을 시행한다.

n = int(input())
origin = [int(n) for n in input().split()] # 4,1,5,2,3
m = int(input())
compare = [int(m) for m in input().split()] # 1,3,7,9,5

origin.sort() # 1,2,3,4,5

for i in range(m): # 
    tag = False
    low = 0
    high = len(origin) -1
    target = compare[i] # 5
    while low <= high:
        mid = (low+high) // 2
        if origin[mid] == target:
            tag = True
            print(1)
            break
        elif origin[mid] > target: 
            high = mid - 1
        else:
            low = mid + 1
    
    if tag is False:
        print(0)

🚩Others submission

다른 사람들의 풀이도 문제의 의도대로 위와 같이 ‘이진탐색’으로 풀었다.

좀 신박했던 코드를 첨부한다. (파이써닉하다)

출처 : **[BOJ] 백준 1920번 수 찾기 (Python)**

# 입력
N = int(input())
A = set(map(int, input().split()))	# 탐색 시간을 줄이기 위해 set으로 받음
M = int(input())
arr = list(map(int, input().split()))

for num in arr:				# arr의 각 원소별로 탐색
    print(1) if num in A else print(0)	# num이 A 안에 있으면 1, 없으면 0 출력

A를 정렬하지 않고 set으로 만들어 탐색하는 방법이다. 속도는 방법1보다 빠르다.

💡TIL

• 이번 문제를 통해 이진탐색에 대해 더 제대로 배우게 된 것 같다. 혼자서 코드를 짜지 못하고 이진탐색 코드 구현하는 법을 본 것을 토대로 남은 코드를 짜긴 했지만, 그래도 배웠다!!!! 요새 스택유형만 보다가 이런 유형을 보고 다지는 것이라 좋게 생각한다.
• 이진탐색에서는 left(low), right(high), mid, target이렇게 4개의 변수가 필요하다. left와 right가 그때그때 값이 바뀌고 left와 right의 값이 따라 mid값도 바뀐다. 이렇게 기준점을 바뀌어가며 target을 찾아간다.