[APS] 백준 10815 : 숫자 카드

개요

문제 : 백준 10815 : 숫자 카드
백준 10815 : 숫자 카드

[문제 분석]

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

[풀이 전략]

풀이 전에 문제를 정리를 해보자.
1. 첫번째 접근 : Brute force

• 쉽게 생각할 수 있는 N에 대한 M의 1대1 전체 탐색(Brute force)
  -> 문제점 시간 복잡도가 N*M이라 구현 시 시간제한에 걸림

2. 두번째 접근 : 이진 탐색

• 시간 복잡도를 낮추기 위해 이진 탐색을 적용해서 풀이 할 수 있다.(nlogn)

[구현코드]

package test;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] Narr = new int[N];
    for(int i = 0; i<N; i++) 
        Narr[i] =  sc.nextInt();
    int M = sc.nextInt();
    int[] Marr = new int[M];
    int[] test = new int[M];
    Arrays.sort(Narr);
  
    for (int j = 0 ; j < M ; j ++) {
        int L = 0;
        int R = Narr.length-1;  
        Marr[j] = sc.nextInt(); 
        while (L <= R ) {
        int mid = (L+R)/2;
        if(Narr[mid] == Marr[j]) {
            test[j] = 1;
            break;}
        else if(Narr[mid] > Marr[j]) 
             R = mid - 1;
        else {
            L = mid + 1;
        }
        
            
        }
        
    }
         
    for (int result : test)
    System.out.print(result+" ");
}
    
}

[개선사항]

1. Set을 이용한 방법
   Set을 이용해서 검색할 때 배열을 확인하지 않기 때문에 가장 적절한 방법이라고 생각이 든다.
   (시간 복잡도 : O(1))

2. 구현 코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

        // 1. N 입력
        int N = sc.nextInt();
        
        Set<Integer> nSet = new HashSet<>();
        
        for(int i = 0; i < N; i++) {
            nSet.add(sc.nextInt());
        }

        int M = sc.nextInt();
        StringBuilder sb = new 	StringBuilder();

        for(int i = 0; i < M; i++) {
            int target = sc.nextInt();

            if (nSet.contains(target)) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }

        System.out.println(sb.toString());
    }
}

---

오늘은 맛있었던 런치야미 끝