[백준] 1920번: 수 찾기 (Java)

문제: https://www.acmicpc.net/problem/1920

📌 문제 탐색하기

입력 : 첫째 줄 - 자연수 N (1 ≤ N ≤ 100,000)
둘째 줄 - N개의 정수
셋째 줄 - 자연수 M (1 ≤ N ≤ 100,000)
넷째 줄 - M개의 정수
출력 : M개의 정수가 N개의 정수 안에 존재하면 1, 존재하지 않으면 0

가능한 시간복잡도

O(log N)

알고리즘 선택

이진탐색

📌 코드 설계하기

1. N, n 배열을 input으로 받는다.
2. 이진탐색을 하기 위해 n 배열을 정렬한다.
3. M, m 배열을 input으로 받는다.
4. m 배열의 각 요소에 대해 Arrays.binarySearch를 사용해 n 배열의 요소가 존재하는지 확인한다.
5. 존재하면 1을 출력하고, 그렇지 않으면 0을 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] n = new int[N];
        for (int i = 0; i < N; i++) {
            n[i] = sc.nextInt();
        }
        
        Arrays.sort(n); //이진탐색을 위한 정렬
        
        int M = sc.nextInt();
        int[] m = new int[M];
        for (int i = 0; i < M; i++) {
            m[i] = sc.nextInt();
        }
        
        for (int x : m) {
           if (Arrays.binarySearch(n, x) >= 0){
               System.out.println(1);
           } else {
               System.out.println(0);
           }
        }
    }
}