[Algo/Boj] 자바 - 수찾기 /1920
[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");
}
}
}
}
Author And Source
이 문제에 관하여([Algo/Boj] 자바 - 수찾기 /1920), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rgunny/AlgoBoj-자바-수찾기-1920저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)