[BaekJoon] 10815번 숫자 카드 문제풀이 (Success)

10815번: 숫자 카드

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int num1 = Integer.parseInt(br.readLine());
 
        String[] sArr1 = new String[num1];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < num1; i++) {
            sArr1[i] = st1.nextToken();
        }
        
        int num2 = Integer.parseInt(br.readLine());
 
        String[] sArr2 = new String[num2];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < num2; i++) {
            sArr2[i] = st2.nextToken();
        }
        
        for(int i=0; i<num2; i++) {
            int j = 0;
            for(j=0; j<num1; j++) {
                if(sArr2[i].equals(sArr1[j])) {
                    bw.write("1 ");
                    break;
                }
            }
            if(j==num1) {
                bw.write("0 ");
            }
        }
        
        bw.flush();
        bw.close();
    }
 
}
 

🚨 이중 for문에 의해서 시간복잡도가 n^2까지 커질 수 있어 시간 초과

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int num1 = Integer.parseInt(br.readLine());
 
        int[] iArr1 = new int[num1];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < num1; i++) {
            iArr1[i] = Integer.parseInt(st1.nextToken());
        }
 
        Arrays.sort(iArr1);
 
        int num2 = Integer.parseInt(br.readLine());
 
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < num2; i++) {
            bw.write(bSearch(iArr1, Integer.parseInt(st2.nextToken())) + " ");
        }
 
        bw.flush();
        bw.close();
    }
 
    public static int bSearch(int[] iArr1, int search) {
        int first = 0;
        int last = iArr1.length - 1;
 
        while (first <= last) {
            int mid = (first + last) / 2;
 
            if (iArr1[mid] == search) {
                return 1;
            }
 
            if (iArr1[mid] < search) {
                first = mid + 1;
            } else {
                last = mid - 1;
            }
        }
 
        return 0;
 
    }
 
}
 

- 이진 탐색

  ⭐ 이진 탐색 대상은 전제 조건으로 정렬되어 있어야 함

    - 상근이가 갖고 있는지 확인해야 할 카드 값을 search로 받아서 상근이의 카드 배열 iArr1과 비교

    - 예시

        - 상근이가 갖고 있는 카드: 0 1 2 3 4 5 6 7 8 9

        - search = 6, first = 0, last = 9, mid = 4

        - search가 더 크므로 시작값을 0 ▶ 5으로 변경

        - search = 6, first = 5, last = 9, mid = 7

        - search가 더 작으므로 끝 값을 9 ▶ 6으로 변경

        - search와 mid가 동일하므로 return 1

 

 

 

🔗 소스 코드
HJ0216/TIL/BOJ

 

📚 참고 자료

[BOJ] 백준 10815번 : 숫자 카드 (JAVA)