2022.01.27 34일차

백준 10815번 (숫자 카드)

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

나의 풀이

1. 정보: 카드 개수 N, 카드에 적혀있는 수, 찾는 개수 M, 찾는 수
2. 해당하는 값 찾기, 범위가 넓어서 이진탐색 활용
3. answer -> M 개수만큼 배열, 기본값은 0으로 설정
4. 카드에 적혀있는 수는 int 배열(nArr)로 오름차순 정렬
5. 인덱스를 기준으로 최소값(min), 최대값(max), 중간값(mid) 설정
6. min<=max 반복문, mid == 찾는 수(value) 해당하는 인덱스 값 1로 변경하고 다음 반복문
7. mid < value, min = mid + 1;
8. mid > value, max = mid - 1;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[] nArr = new int[N];

        for(int i = 0; i < N; i++) {
            nArr[i] = scanner.nextInt();
        }

        Arrays.sort(nArr);

        int M = scanner.nextInt();
        int[] answer = new int[M];

        for(int x = 0; x < M; x++) {
            int min = 0;
            int max = N - 1;
            int value = scanner.nextInt();

            while(min <= max) {
                int mid = (min + max) / 2;
                if (nArr[mid] == value) {
                    answer[x] = 1;
                    break;
                } else if (nArr[mid] < value) {
                    min = mid + 1;
                } else if (nArr[mid] > value) {
                    max = mid - 1;
                }
            }
        }

        for (int i : answer) {
            System.out.print(i + " ");
        }

    }
}

생각하기