[백준] 1920번 : 수 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1920번: 수 찾기

 

1. 문제 설명

2. 풀이과정

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 정수의 개수를 입력받는다. N = int(sys.stdin.readline())
3. 각 정수를 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
4. 테스트 횟수를 입력받는다. M = int(sys.stdin.readline())
5. 각 테스트 수를 입력받아 리스트로 저장한다. B = list(map(int, sys.stdin.readline().split()))
6. 입력받은 정수의 리스트를 이분 탐색으로 비교하기 위해 오름차순 정렬한다. A.sort()
7. 각 테스트 수를 하나씩 추출한다. for i in B
8. 테스트 수가 정수 리스트에 있는지 결과를 저장할 변수를 생성하고 초기화한다. answer = 0
9. 만약 테스트 수가 정수 리스트의 수 안에 있다면 if (A[0] <= i and i <= A[-1])
10. 찾을 범위의 인덱스 시작 값을 0으로 s = 0
11. 끝 값을 리스트의 마지막 인덱스 값으로 지정한다. e = N - 1
12. 시작 인덱스 값이 끝 인덱스 값을 넘어갈 때까지 반복한다. while (s <= e)
13. 가운데 지점 인덱스 값을 구한다. center = (e + s) // 2
14. 만약 가운데 값이 찾는 값과 일치하면 if (i == A[center])
15. 값이 존재하므로 결과를 1로 변경하고 answer = 1
16. 반복을 종료한다. break
17. 만약 찾는 값이 가운데 값보다 작으면 elif (i < A[center])
18. 끝 인덱스를 가운데 인덱스 앞으로 변경한다. e = center - 1
19. 만약 찾는 값이 가운데 값보다 크면 else
20. 시작 인덱스를 가운데 인덱스 뒤로 변경한다. s = center + 1
21. 결과를 출력한다. print(answer)

반응형

3. 소스코드

import sys

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

M = int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split()))

A.sort()

for i in B:
    answer = 0
    if (A[0] <= i and i <= A[-1]):
        s = 0
        e = N - 1

        while (s <= e):
            center = (e + s) // 2
            if (i == A[center]):
                answer = 1
                break
            elif (i < A[center]):
                e = center - 1
            else:
                s = center + 1

    print(answer)