코딩 테스트 [탐색] - 원하는 정수 찾기

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

(시간 제한 2초)

---

입력

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

출력

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

예제 입력
5	// 데이터 개수
4 1 5 2 3
5	// 찾아야 할 숫자 개수
1 3 7 9 5

예제 출력
1
1
0
0
1

---

1단계 - 문제 분석하기

N의 최대 범위가 100,000이므로 단순 반복문으로는 문제를 풀 수 없다. 이진 탐색을 적용하면 O(nlogn) 시간 복잡도로 해결할 수 있으므로 이진 탐색을 적용하면 풀 수 있다.
이진 탐색은 정렬을 가정하므로 정렬 함수도 사용한다.

2단계 - 손으로 풀어 보기

1 탐색 데이터를 1차원 배열에 저장한 다음 저장된 배열을 정렬한다.

2정수 X가 존재하는지 이진 탐색을 사용해 확인한다.

3단계 - sudo코드 작성하기

N(정렬할 수 개수) M(탐색할 정수 개수)
A(정렬할 배열 선언)

for(N의 개수만큼 반복)
{
	A 배열 저장
}
A 배열 정렬

for(M의 개수만큼 반복)
{
	target(찾아야 하는 수)
	start(시작 인덱스) end(종료 인덱스)

	while(시작 인덱스 <= 종료 인덱스)
    {
    	mid(중간 인덱스)
        if(중간값 > target)
        	종료 인덱스 = 중간 인덱스 - 1
        else if(중간값 < target
        	시작 인덱스 = 중간 인덱스 + 1
        else
        	정수 발견. 반복문 종료
    }
    
    if(정수 발견)
    	1 출력
    else
    	0 출력
}

4단계 - 코드 구현하기

import java.util.Arrays;
import java.util.Scanner;

public class Q29 {
    static int N;
    static int M;
    static int[] A;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        A = new int[N];
        for(int i = 0; i < N; i++)
            A[i] = sc.nextInt();

        Arrays.sort(A);

        M = sc.nextInt();

        for(int i = 0; i < M; i++){
            boolean find = false;
            int target = sc.nextInt();
            int start = 0;
            int end = N-1;

            while(start <= end){
                int mid = (start + end) / 2;
                int mid_value = A[mid];
                if(mid_value < target)
                    start = mid + 1;
                else if (mid_value > target)
                    end = mid - 1;
                else{
                    find = true;
                    break;
                }
            }

            if(find == true)
                System.out.println(1);
            else
                System.out.println(0);
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편