[백준 알고리즘 / JAVA] 10815번 숫자 카드

---

문제 정보

• 문제 링크: https://www.acmicpc.net/problem/10815
• 문제 번호: 10815번
• 문제 이름: 숫자 카드
• 문제 난이도: 실버5
• 반복 학습 날짜
  • 2024.01.07 완료

10815번: 숫자 카드

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // BufferedReader와 StringTokenizer를 사용한 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 배열의 크기 N저장
        int N = Integer.parseInt(st.nextToken());

        // "nArray"배열을 초기화
        int[] nArray = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nArray[i] = Integer.parseInt(st.nextToken());
        }

        // "nArray"배열을 오름차순으로 정렬
        Arrays.sort(nArray);

        // 배열의 크기 M저장
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());

        // "mArray"배열을 초기화
        int[] mArray = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            // 두 번째 배열의 각 요소에 대해 첫 번째 배열에서 이진 탐색 수행
            int target = Integer.parseInt(st.nextToken());
            mArray[i] = binarySearch(nArray, target);
        }

        // 두 번째 배열의 각 요소에 대한 이진 탐색 결과 출력
        for(int i = 0; i < mArray.length; i++) {
            System.out.print(mArray[i] + " ");
        }
    }

    // 목표 값이 배열에 존재하는지 확인하는 이진 탐색 함수
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        // 이진 탐색 루프
        while(left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] == target) {
                // 목표 값이 발견되면 1을 반환
                return 1;
            } else if(arr[mid] < target) {
                // 목표 값이 중간 요소보다 크면 오른쪽 반을 탐색
                left = mid + 1;
            } else {
                // 목표 값이 중간 요소보다 작으면 왼쪽 반을 탐색
                right = mid - 1;
            }
        }
        // 목표 값이 발견되지 않으면 0을 반환
        return 0;
    }
}

---

풀이

Step1: 이진 탐색 알고리즘 정의

// 목표 값이 배열에 존재하는지 확인하는 이진 탐색 함수
public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    // 이진 탐색 루프
    while(left <= right) {
        int mid = (left + right) / 2;
        if(arr[mid] == target) {
            // 목표 값이 발견되면 1을 반환
            return 1;
        } else if(arr[mid] < target) {
            // 목표 값이 중간 요소보다 크면 오른쪽 반을 탐색
            left = mid + 1;
        } else {
            // 목표 값이 중간 요소보다 작으면 왼쪽 반을 탐색
            right = mid - 1;
        }
    }
    // 목표 값이 발견되지 않으면 0을 반환
    return 0;
}

• 탐색할 배열의 시작("left")과 끝("right") 인덱스를 초기화합니다.
• "left"가 "right"보다 작거나 같을 동안 반복 수행합니다.
  
  • 중간 인덱스("mid")를 계산하고 인덱스의 값과 목표 값을 비교
  • 목표 값이 중간 값과 같다면 1을 반환하고 종료
  • 목표 값이 중간 값보다 크면 "left"를 중간 값의 다음으로 조정하여 오른쪽 반을 탐색 수행
  • 목표 값이 중간 값보다 작으면 "right"를 중간 값의 이전으로 조정하여 왼쪽 반을 탐색 수행
• 위 반복 수행 후 목표 값이 발견되지 않으면 0을 반환합니다.