[Java+Python]1920번, 수 찾기

목차

 

이진 탐색

 

[Java+Python]1654번, 랜선 자르기

[Java+Python]2805번, 나무 자르기

[Java+Python]2110번, 공유기 설치

[Java+Python]2805번, K번째 수

[Java+Python]12015번, 가장 긴 증가하는 부분 수열 2

문제

 

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을 출력한다.

 

풀이

 

이진 탐색의 첫 번째 문제이다. 이전 글에서 적은 이진 탐색의 예제와 사실상 같은 문제라 더 설명할 것은 없어 보인다.

 

코드 구현 알고리즘으로 바로 들어가자면 아래와 같이 진행된다.

 

1. 크기가 n인 배열(리스트)를 입력받아 오름차순으로 정렬한다.
2. 크기가 m인 배열(리스트)를 numbers에 저장한다.
3. 결과를 저장할 문자열 result를 생성 및 초기화해준다.
4. numbers의 각 요소 number를 순서대로 탐색하며 아래와 같이 이진 탐색을 진행한다.
   
   
   1. 존재여부를 저장할 isFound를 false로 초기화한다.
   2. 전체 구간 탐색을 위해 left = 0, right = n - 1로 초기화한다.
   3. left <= right인 동안 아래와 같은 탐색을 반복한다.
      
      
      1. 인덱스의 중간값 (left + right) / 2 를 mid에 배정한다.
      2. arr[mid]와 number의 값을 비교한 뒤
         
         
         1. arr[mid] == number → isFound를 true로 갱신하고 반복을 종료한다.
         2. arr[mid] < number → left를 mid + 1로 갱신한다. 
         3. arr[mid] > number → right를 mid - 1로 갱신한다.
   4. 삼항 연산자를 사용해 isFound의 값에 따라 1 또는 0을 개행문자와 함께 result에 추가한다.
5. result를 출력한다.

잘게 쪼개고 보니 길어 보이지만 이해나 구현 자체가 그리 어렵지는 않다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Prob1920 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		int m = Integer.parseInt(br.readLine());
		int[] numbers = new int[m];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < m; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}

		StringBuilder result = new StringBuilder();

		for (int number : numbers) {
			boolean isFound = false;
			int left = 0;
			int right = n - 1;

			while (left <= right) {
				int mid = (left + right) / 2;

				if (arr[mid] == number) {
					isFound = true;
					break;
				} else if (arr[mid] < number) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			}

			result.append(isFound? 1 : 0).append('\n');
		}

		System.out.println(result.toString());
	}
}

 

Python

 

import sys

n = int(sys.stdin.readline().rstrip())
lst = list(map(int, sys.stdin.readline().rstrip().split(' ')))
lst = sorted(lst)
m = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split(' ')))

result = ''

for number in numbers:
    isFound = False
    left = 0
    right = n - 1

    while left <= right:
        mid = (left + right) // 2

        if lst[mid] == number:
            isFound = True
            break
        elif lst[mid] < number:
            left = mid + 1
        else:
            right = mid - 1

    result += str(1 if isFound else 0) + '\n'

print(result)

 

Performance