수 찾기

문제

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보다 작다.

• N 개의 정수 배열
• M 개의 정수 배열
• M 배열의 정수가 N 배열에 있는지 판단하여 1,0 출력
• 정수 범위 -2^31 <= 정수 < 2^31

 

출력

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

 

---

해결방법

1. 절차적

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] queries = new int[m];
        for (int i = 0; i < m; i++) {
            queries[i] = sc.nextInt();
        }

        Arrays.sort(arr);  // O(n log n)
        
        // 바이너리 서치, O(log n)
        for (int q : queries) {
            // 내장 기능 사용, 반환값 ≥ 0 이면 찾음, 음수면 없음
            System.out.println(Arrays.binarySearch(arr, q) >= 0 ? 1 : 0);
            // 로직 구현
            if(binarySearch(arr, q){
            	System.out.println(1);
            } else {
            	System.out.println(0);
            }
        }
        
        private static boolean binarySearch(int[] arr, int target) {
            int left = 0, right = arr.length - 1;

            // 이진 탐색이 계속 실행될 조건
            while (left <= right) {
                int mid = (left + right) / 2;
                // 이진 탐색에서 타켓을 찾았는지 확인
                if (arr[mid] == target) {
                    return true;
                }
                // 타겟 값이 중간 값보다 큰 경우의 조건
                else if (arr[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return false;
        }
    }

 

2. 객체

• 재사용성과 확장성이 용이
• 검색 방식을 바꿀 때, NumberFinder를 수정하면 된다.
• 테스트 용이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        NumberFinder finder = new NumberFinder(arr);

        int m = sc.nextInt();
        while (m-- > 0) {
            int q = sc.nextInt();
            System.out.println(finder.contains(q) ? 1 : 0);
        }
    }
}

public class NumberFinder {
    private final int[] data;

    public NumberFinder(int[] data) {
        Arrays.sort(data);
        this.data = data;
    }

    public boolean contains(int target) {
        return Arrays.binarySearch(data, target) >= 0;
    }
}

 

 

3. 알고리즘

문제: 정렬 O(n log n) + 매번 이진탐색 O(log n) → 전체 O(n log n + m log n)
해결: 해시나 비트마스크를 이용해 O(n + m)으로 줄이기

3.1 HashSet

• 시간 복잡도: O(n + m) (평균)
• 단점: 해시 충돌 드물지만, 최악 O(n) 가능 / 메모리 사용량이 다소 증가

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class FindWithHash {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> set = new HashSet<>(n * 2);
        for (int i = 0; i < n; i++) {
            set.add(sc.nextInt());
        }

        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            System.out.println(set.contains(sc.nextInt()) ? 1 : 0);
        }
    }
}

  

3.2 BitSet 

• 시간 복잡도: O(n + m), 공간: 약 2 000 001 bool (≈2 MB)
• 장점: 가장 빠른 상수 시간 조회

import java.util.Scanner;

public class FindWithBitset {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int OFFSET = 1_000_000;
        boolean[] present = new boolean[2 * OFFSET + 1];

        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            present[sc.nextInt() + OFFSET] = true;
        }

        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int q = sc.nextInt() + OFFSET;
            System.out.println((q >= 0 && q < present.length && present[q]) ? 1 : 0);
        }
    }
}

 

결론

• 간단히 한두 번만 돌려볼 때는 절차적
  
  • 장점: 코드 흐름이 직관적이라 로직을 파악하기 쉽고, 한 번만 실행하거나 간단한 스크립트 형태로 처리할 때 빠르게 구현할 수 있습니다.
  • 단점: 기능이 늘어날수록 함수나 전역 변수가 여기저기 얽히기 쉬워 유지보수가 어려워지고, 재사용성도 떨어집니다.
• 앞으로 기능이 추가되거나 테스트·재사용을 염두에 뒀다면 객체지향
  
  • 장점: 데이터와 동작을 클래스로 묶어 역할을 명확히 분리하므로 확장성·재사용성이 높고, 단위 테스트도 용이합니다.
  • 단점: 구조 설계·추상화에 드는 초기 작업량이 늘어나고, 작은 문제에 과도하게 복잡해질 수 있습니다.
• 수백만 건 이상의 빈번한 조회가 필요하다면 해시셋/비트셋 기반 알고리즘
  
  • 장점: 해시셋이나 비트셋 같은 자료구조를 이용하면 검색을 O(1)에 가깝게 처리할 수 있어 대량 데이터·반복 질의에 최적화됩니다.
  • 단점: 해시셋은 객체 오버헤드가 크고, 비트셋은 범위 전체 메모리를 선점하므로 메모리 트레이드오프가 있습니다.