[Algorithm/BOJ] 자바 - 수찾기/1920

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
수찾기	BOJ	Silver 4	Binary Search	풀이	문제

풀이

이분 탐색(Binary Search)로 푸는 간단한 문제입니다.

이번 포스트에서는 이분 탐색이 아닌, set의 개수를 비교하여 아이디어로 간단하게 풀어보았습니다.

n개의 정수를 set에 담은 뒤, m개의 수를 차례대로 set에 추가하며 set의 크기가 변함의 유무에 따라 답을 출력하였습니다.

HashSet은 Set 인터페이스의 구현 클래스입니다. Set 자료구조는 객체를 중복해서 저장할 수 없고, 저장 순서가 보장되지 않습니다.

• 저장 순서를 유지해야 할 시 : LinkedHashSet 클래스 사용
• 정렬이 필요할 시 : TreeSet 클래스 사용

Set 자료구조 시간복잡도

Class Name	Add	Contains	Next
HashSet	O(1)	O(1)	O(h/n)
LinkedHashSet	O(1)	O(1)	O(1)
EnumSet	O(1)	O(1)	O(1)
TreeSet	O(log n)	O(log n)	O(log n)

코드

package me.rgunny.algo.boj.etc;

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

/**
 * BOJ_1920
 *  수 찾기
 *  https://www.acmicpc.net/problem/1920
 */
public class BOJ_1920 {

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

        HashSet set = new HashSet();

        int n = sc.nextInt(); // n개의 정수
        for (int i = 0; i < n; i++) {
            set.add(sc.nextInt());
        }

        int m = sc.nextInt(); // m개의 수
        for (int i = 0; i < m; i++) {
            int size = set.size();
            set.add(sc.nextInt());

            if (size == set.size()) {
                System.out.println("1");
            }

            else {
                System.out.println("0");
            }
        }

    }
}