[백준/JAVA] 10815번: 숫자 카드

🔺 문제

10815번: 숫자 카드

 

🔺 코드

- 틀림 (시간 복잡도 : O(MN) )

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

public class Main {
	public static void main(String[] args) throws IOException {
		var br = new BufferedReader(new InputStreamReader(System.in));
		
        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];
        
        var st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i< N ; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }
        
        int M = Integer.parseInt(br.readLine());
        int[] arr2 = new int[M];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < M ; i++) {
            int num = Integer.parseInt(st.nextToken());
            
            for(int j = 0 ; j < N ; j++) {
                if(num == arr1[j]) {
                    arr2[i] = 1;
                }
            }
        }
        
        for(int i : arr2) {
            System.out.print(i + " ");
        }
	}
}

시간 초과가 뜸

 

 

 

 

- 정답 (시간 복잡도 : O((M+N)logN))

 

[BOJ] 10815번 숫자카드 자바(java) 풀이 (이진탐색)

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

public class Main {
    static int[] cards;
    
	public static void main(String[] args) throws IOException {
		var br = new BufferedReader(new InputStreamReader(System.in));
		
        int N = Integer.parseInt(br.readLine());
        cards = new int[N];
        
        var 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 result = binarySearch(Integer.parseInt(st.nextToken()));
            
            if(result != -1) sb.append(1 + " ");
            else             sb.append(0 + " ");
        }
        
        System.out.println(sb.toString());
	}
	
	// 이진 탐색
	private static int binarySearch(int target) {
	    int left = 0;
	    int right = cards.length - 1;
	    int mid;
	    
	    while(left <= right) {
	        mid = (left + right) / 2;
	        
	        if(cards[mid] < target)       left = mid + 1;
	        else if(cards[mid] > target)  right = mid - 1;
	        else                          return mid;
	    }
	    return -1;
	    
	} 
	
}

✅ 해결 아이디어
- 이진 탐색!

처음에 이진 탐색 아닌걸로 했다가 이진 탐색으로 컴백,,,

---

🔺 다른 풀이들

- 풀이1) Set 활용

백준 10815 숫자 카드[Java]

Set - contains를 활용하셨다.

 

 

- 풀이2) Map 활용

[백준-10815번/Java] 숫자 카드

Map - get을 활용하셨다.

 

---

💬 느낀 점

이진 탐색... 오랜만에 보았는데... 꼭 마스터해야겠다.. 복습 필수...

다'이진',,,,!!

---

(참고)

✔ 이진 탐색 메소드에서 받는 인자가 약간씩 다른 풀이들

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

[알고리즘] 백준 10815 숫자 카드 -이분탐색- 자바

 

 

백준 10815번(자바)

 

 

 

✔ 이진 탐색