AlgorithmBOJ

백준 숫자카드 10815

, , ,

1. 문제 링크

백준 숫자카드 10815

2. 문제 조건

문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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보다 작거나 같다

3. 컴퓨팅 사고

  • 1,2번째 줄에 입력에 상근이가 가지고 있는 카드의 개수를 저장시킵니다.
  • 3,4번째 줄에 찾고자하는 숫자를 입력합니다.

처음에 모든 경우의 수를 탐색하게 된다면 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 라는 조건때문에 시간복잡도 상으로 시간초과가 날 것으로 생각하였습니다. 그래서 HashSet과 이분탐색을 진행하여 해당 문제를 풀어보면 시간복잡도면에서 통과할 수 있을것이라는 생각이 들게되었습니다. 해당 포스팅에는 HashSet과 이분탐색을 이용한 풀이를 두가지 방법을 모두 사용해보았습니다.

3.1. HashSet을 사용한 풀이

문제조건상 반복되는 수가 없다고 하였지만, Map을 사용하기에는 (key, value)가 필요하기 때문에 HashSet을 사용하였습니다. 상근이가 가진 카드를 모두 HashSet에 넣어주게 된다음에 이제 상근이가 찾을 값들을 HashSet에 있는 값과 비교해주면 됩니다. 찾았다면 1, 찾지못했다면 0을 add시켜주게 되고 ArrayList 자료 구조를 사용하여 최종 결과값을 출력시켜주었습니다.

HashSet의 특징
자바 Collection 중 Set의 대표적인 HashSet 클래스입니다. HashSet은 Set 인터페이스의 구현 클래스입니다. HashSet은 Set의 파생클래스로 Set은 기본적으로 집합으로 중복된 원소를 허용하지 않으며 순서 또한 고려하지 않습니다.

3.2. Binary Search(이분 탐색)

이분 탐색이란?
이진 탐색은 정렬된 데이터의 집합을 이분화 하면서 탐색하는 알고리즘입니다.

이분 탐색의 장점
정렬이 되어 있어야 이진탐색을 할 수 있습니다.O(logN) 으로 빠르게 탐색할 수 있습니다. O(logN)인 이유는 이진 트리형태로 절반을 줄여가면서 값을 탐색하는 형식이기 때문입니다.
이분 탐색의 단점
만약 이분탐색에서 값들이 정렬이 되어 있지 않다면 정렬하는데 많은시간이 소요되며 정렬된 데이터가 아니면 이분탐색에 적용할 수 없습니다.

이진탐색 문제 풀이

  • 상근이가 가진 카드의 값들을 입력을 받습니다.
  • 상근이가 가진 카드의 값들을 정렬합니다(오름차순정렬)
  • 상근이가 찾고하자는 개수까지 Binary Search함수를 호출합니다. 이때 첫번째 파라미터는 찾고자하는 target 값입니다. 그리고 두번째 파라미터는 상근이가 가지고 있는 카드의 개수입니다.

binary Search함수

  • 시작점은 0, 끝점은 len-1의 값으로 초기화 시켜줍니다.
  • while문으로 end보다 크거나 작을때 까지 계속 루프를 진행합니다.
  • mid라는 변수를 선언하여 시작점과 끝점을 더한값의 / 2를 연산하여 중간값을 구해주게 됩니다.
  • 만약 상근이가 가진 카드의 값이 target값 보다 작을 경우 시작점을 start = mid-1점으로 설정하게 됩니다.
  • 만약 상근이가 가진 카드의 값이 target값 보다 클 경우 끝점을 end = mid-1로 설정하게 됩니다.
  • 상근이가 가진값과 찾고자하는 값이 같을 경우에는 현재 중간값을 리턴해주게 됩니다. 즉, 상근이가 갖고 있는 카드에서 상근이가 찾고자하는 값을 찾은게 됩니다.
  • 해당 binary search함수는 값을 찾았기 때문에 중간값을 리턴해줍니다. 찾았을 경우에는 1을 넣어주게 됩니다.
  • 값을 찾지 못하였을 경우에는 -1을 리턴을 받습니다. 그리고 0을 넣어주게됩니다.
  • 최종적으로 값을 출력시키게 되면 해당되는 값을 찾았는지 못찾았는지의 여부를 확인할 수 있습니다.(0,1)

4. 소스 코드

Binary Search(이분탐색) 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 숫자카드 {
    static int[] arr;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> answer = new ArrayList<>();
        arr = new int[n];
        
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<m; i++){
            int x = Integer.parseInt(st.nextToken());
            // none contain
            if(BinarySearch(x,n) == -1){
                answer.add(0);
            }else {
                answer.add(1);
            }
        }
        for (Integer value : answer) {
            System.out.print(value + " ");
        }
    }

    static int BinarySearch(int target, int len) {
        int start = 0;
        int end = len-1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(arr[mid] < target){
                start = mid+1;
            }else if(arr[mid] > target){
                end = mid-1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}

HashSet 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class 숫자카드 {
    // HashSet 문제
    public static void main(String[] args) throws IOException {
        ArrayList<Integer> arr = new ArrayList<>();
        HashSet<Integer> s = new HashSet<Integer>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++){
            s.add(Integer.parseInt(st.nextToken()));
        }
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++){
            int num = Integer.parseInt(st.nextToken());

            if(s.contains(num)){
                arr.add(1);
            }else {
                arr.add(0);
            }
        }
        for (Integer value : arr) {
            System.out.print(value + " ");
        }
    }
}
Share