[백준알고리즘] 10815. 숫자 카드 풀이 (Java)

❓ 문제

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

❗ 틀린 내 풀이

처음 내 풀이

import java.io.IOException;
import java.util.Scanner;
import java.util.Arrays;

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

        int N = sc.nextInt();
        int[] usrCard = new int[N];
        for(int i = 0; i < N; i++){
            usrCard[i] = sc.nextInt();
        }
        
        int M = sc.nextInt();
        int[] compareCard = new int[M];
        for(int i = 0; i < M; i++){
            compareCard[i] = sc.nextInt();
        }

        for(int i = 0; i < M; i++){
            int key = compareCard[i];
            int result = Arrays.stream(usrCard).anyMatch(x -> x == key) ? 1 : 0;
            System.out.print(result + " ");
        }
    }
}

java의 anyMatch함수를 사용하여 문제를 풀었으나 시간 초과 오류가 발생하였다.

다른 사람의 풀이를 참조하니 그 이유를 알게 되었다.

❗ 다른 사람의 풀이

위 문제는 선형탐색으로 풀게 될 경우 시간복잡도가 ON(MN)으로 시간 초과가 발생한다.

따라서 O(logN)인 이분탐색을 사용해 O(MlogN)만큼 줄여야한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine()); // 카드의 개수
        int[] cards = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(cards); // 이분탐색할 배열은 정렬되어 있어야 함.
        int M = Integer.parseInt(br.readLine()); // 구별할 수의 개수
 
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int temp = Integer.parseInt(st.nextToken());
            sb.append(binarySearch(cards, N, temp) + " ");
        }
 
        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static int binarySearch(int[] cards, int N, int search) {
        int first = 0;
        int last = N - 1;
        int mid = 0;
 
        while (first <= last) {
            mid = (first + last) / 2; // 중간 인덱스
 
            if (cards[mid] == search) { // 중간값과 찾으려는 수가 같은 경우
                return 1;
            }
 
            if (cards[mid] < search) { // 중간값이 찾으려는 수보다 작으면, 그 이하로는 볼 필요 없음.
                first = mid + 1;
            } else { // 중간값이 찾으려는 수보다 크면, 그 이상으로는 볼 필요 없음.
                last = mid - 1;
            }
        }
 
        return 0;
    }
}

 

❗ 수정한 내 풀이

아직 bufferReader와 bufferWriter 쓰는 거에 익숙하지 않아서 Scanner로 풀었다.

시간 초과에 대해 찾아보다보니 Scanner가 bufferReader를 쓰는 것보다 느리다는 것을 알게 되었다.

bufferReader를 쓰는 연습을 조금 더 해야겠다!!

import java.io.IOException;
import java.util.Scanner;
import java.util.Arrays;

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

        int N = sc.nextInt();
        int[] usrCard = new int[N];
        for(int i = 0; i < N; i++){
            usrCard[i] = sc.nextInt();
        }

        Arrays.sort(usrCard);
        
        int M = sc.nextInt();
        int[] result = new int[M];
        for(int i = 0; i < M; i++){
            int compareNum = sc.nextInt();
            result[i] = getContainCard(usrCard, N, compareNum);
        }

        for(int i = 0; i < M; i++){
            System.out.print(result[i] + " ");
        }
    }

    public static int getContainCard(int[] cards, int N, int search) {
        int start = 0;
        int last = N - 1;
        int mid = 0;

        
        while(start <= last) {
            mid = (start + last) / 2;
            if(cards[mid] == search) {
                return 1;
            }

            if(cards[mid] < search) {
                start = mid + 1;
            } else {
                last = mid - 1;
            }
        }
        return 0;
    }
}

🚩 Detail

• 날짜 : 2022.06.10
• 단계 : 12. 집합과 맵
• 제목 : 숫자 카드
• URL : https://www.acmicpc.net/problem/10815

 

📌참고

•  https://steady-coding.tistory.com/40