[B0J]수 찾기(1920번)

티어 : Sliver 4
정답여부 : 정답
알고리즘 유형 : 자료 구조, 정렬, 이분 탐색, 해시를 사용한 집합과 맵
시간 제한 : 1초

💡문제

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

💡출력

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

💡예제 입력1

5
4 1 5 2 3
5
1 3 7 9 5

💡예제 출력1

1
1
0
0
1

💡문제 분석 요약

• 첫줄에 나열한 수중 네번째에 나열한 수가 존재 하면 1 아니먄 0을 출력

💡알고리즘 설계

• Number : 나열된 수
• findNumber : 값이 있는지 없는지 확인하는 수

1. 이분탐색을 통헤 findNumber가 number의 mid보다 작으면 hi값을 mid -1
2. 만약 반대인 경우 lo값을 + 1
3. 만약 값이 존재하는 경우 1을 그렇지 않는 경우 0을 출력

💡시간복잡도

• O(logN)

💡코드

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] Number = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            Number[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(Number);
        
        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int findNumber = Integer.parseInt(st.nextToken());
            sb.append(BinarySearch(Number, findNumber)).append("\n"); // 이분 탐색 결과를 추가하고 줄바꿈
        }
        System.out.print(sb.toString());
    }

    private static int BinarySearch(int[] number, int findNumber) {
        int lo = 0;
        int hi = number.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (findNumber < number[mid]) {
                hi = mid - 1;
            } else if (findNumber > number[mid]) {
                lo = mid + 1;
            } else {
                return 1; // 찾는 값이 배열에 존재할 경우 1 반환
            }
        }
        return 0; // 찾는 값이 배열에 존재하지 않을 경우 0 반환
    }
}

💡 틀린 이유

틀린건 없었다….단지 헷갈리는 부분이 있었을뿐..!

해쉬맵을 이용한 방법도 풀어봤다.

💡 틀린 부분 수정 or 다른 풀이

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 첫 번째 입력: N
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> numberMap = new HashMap<>();
        
        // 두 번째 입력: N개의 숫자
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int number = Integer.parseInt(st.nextToken());
            numberMap.put(number, numberMap.getOrDefault(number, 0) + 1);
        }
        
        // 세 번째 입력: M
        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        // 네 번째 입력: M개의 숫자
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int findNumber = Integer.parseInt(st.nextToken());
            if (numberMap.containsKey(findNumber)) {
                sb.append(1).append("\n"); // 찾는 값이 해시맵에 존재할 경우 1 추가
            } else {
                sb.append(0).append("\n"); // 찾는 값이 해시맵에 존재하지 않을 경우 0 추가
            }
        }
        
        // 결과 출력
        System.out.print(sb.toString());
    }
}​

 

💡 느낀점 or 기억할정보

해쉬맵은 뭔가 메서드만 알면 풀기 쉽고 이분탐색은 알고리즘을 이해하면 문제 구현이 쉬운거 같다.