백준 1920. 수찾기 (set(), Binary Search)

문제

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

틀린 내 풀🦷

# 1920. 수찾기
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, sys.stdin.readline().split()))

M = int(input())
arr_2 = list(map(int, sys.stdin.readline().split()))
result = []

for j in range(M):
    one = []
    for i in range(N):
        if arr[i] == arr_2[j]:
            one.append(1)
            break
        else:
            one.append(0)

    # print(one)
    cnt = 0
    for k in one:
        if k == 1:
            cnt += 1
    if cnt >= 1:
        result.append(1)
    else:
        result.append(0)

for k in result:
    print(k)

구직구직하게 짜기 달인이 되버린 나,,,,

단계별 풀이로 안들어가고 성공률로 들어가서 안 풀어져 있는거 풀어가지고

어떤 방식으로 풀어야하는지 힌트(이차원 배열이다, 정렬이다, 이진탐색이다 이런거)가 없어서 어카지 하다가

찾아야할 값이 주어진 arr_2 리스트를 돌라면서 arr을 돌리는 완전 탐색으로 찾아서 있으면 더해주면 되겠다..

싶었고 무슨일로 인덱스 아웃오브레인지도 안나고 한번에 성공했는디.... 했는데.... 제출했는데...

했는데 시간초과가 나버렸다 ㅋㅋ 혹시나 몰라서 import sys로도 바꿔봤는데 실패....ㅜㅜ

수정된 내 풀🦷

백준에서 풀다가 막히면 질문게시판 들어가서 종종 힌트를 얻는데

나처럼 구질구질하게 푸는 사람이 없었고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

set을 사용하여 입력받아 시간을 적게 걸리게 하는 방법이나 이진 탐색을 사용하였다!!

그러고 보니 이진 탐색을 이용하면 되었는데 혼자서 브로노마스(무지성)으로 하고있었다....

 

 

그래서 먼저 해본 set() 으로 입력 받기 =>

N = int(input())
arr = set(map(int, input().split())) # 출력 시간을 줄이기 위해 set 받음

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

for i in arr_2:
    if i in arr: print(1)
    else: print(0)

결과는 성공~~~~~

set을 자주 안 쓰다보니 어떤 부분에서 쓸지 몰랐는데

입력을 set으로 받아 사용한다는 점을 알게 되었다!!

이진탐색으로 풀은 내 풀🦷

또 다른 방법중에 하나인 바이너리 서치를 통한 방법도 많이 보여서 도전해 보았다~~

N = int(input())
arr = list(map(int, input().split()))
arr.sort() # 이진탐색은 정렬된 것들 탐색하는데 이 부분 기억을 못해서 무한 루프로 몇번 다녀왔다
M = int(input())
arr_2 = list(map(int, input().split()))

for i in arr_2:
    # 바이너리 서치 활용하기(이진탐색)
    result = False 
    start = 0 # 시작 인덱스
    end = N - 1 # 끝 인덱스

    while start <= end:
        mid = ((start + end) // 2) # 중간값의 위치에 해당하는 수와 목표 비교해 나감
        if i == arr[mid]: # 중간값과 목표값이 같다면
            result = True
            break
        elif i > arr[mid]:
            start = mid + 1
        else:
            end = mid - 1

    if result:
        print(1)
    else:
        print(0)

시험에도 나오기는 했지만 오랜만에 이진탐색을 사용해서 계속 틀린값이 나오고

무한루프로 잠시 먼나라이웃나라 다녀왔다....

중간값과 목표값을 비교하면서 시작점이 마지막점보다 넘어서면 종료되는 기저조건을 설정하였다!!!!

 

참고함면 좋을 개념들 ✍️

1) 이진 검색(Binary Search)

:  자료의 가온데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

 => 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다

 

- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다(정렬이 아니라 뒤에 수가 앞에 수보다 커버리면 오바자나.. 찾을 수가 없음!!!!!! 주의!!!!!!!!1..)

 

- 검색 과정

1. 자료의 중앙에 있는 원소를 고른다
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다
3. 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행, 크다면 자료의 오른쪽 반에 대해서 세로 검색을 수행
4. 찾고자 하는 값을 찾을 떄까지 1~3의 과정을 반복한다
5. 찾는다면 성공, 못 찾으면 실패

- 구현

• 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다 => while의 종료 조건을 잘 설정하기
• 이진 검색의 경우, 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요

# 이진 검색 알고리즘
def binarySweach(a, N, key):
	start = 0  # 시작점 
    end = N -1  # 종료점
    while start <= end:
    	middle = (start + end) // 2 # 몫으로 하는 이유 : 나누기 연산자를 사용하면 .0으로 float되걸랑
        if a[middle] == key: # 검색 성공
        	 return true
        elif a[middle] > key:
        	 end = middle - 1
        else:
        	start = middle + 1
    return flase # while 문을 다 돌았는데도 찾지못한다면 검색 실패