-
[백준] 10815번 : 숫자 카드 - 자바(JAVA)알고리즘/백준 2022. 6. 15. 00:01
문제 해석
int형 범위내의 N개의 숫자가 주어집니다.
이때 M개의 숫자가 다시 주어지고 M개의 숫자가 N개의 숫자에 존재하는지 탐색하는 문제입니다.
문제 풀이 전 설계
N제한이 50만이기 때문에 O(N^2)은 불가능합니다.
또한 문제에서는 정렬/이분 탐색으로 문제를 해결하라고 제시했지만 더 효율적인 방법인 HashSet을 이용하면 O(1)의 시간복잡도로 해결이 가능할 것 같습니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main_10815_숫자카드 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); //숫자를 담아둘 집합 Set 선언 Set<Integer> numbers = new HashSet<>(); StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=0; i<N; i++){ numbers.add(Integer.parseInt(st.nextToken())); } //숫자 입력 끝 //true = 1 / false = 0인 결과를 담을 리스트 List<Integer> result = new ArrayList<>(); int M = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); for(int i=0; i<M; i++){ int curNum = Integer.parseInt(st.nextToken()); //집합에 curNum이 포함되어있는지 검사 if(numbers.contains(curNum)){ //포함되어있으면 리스트에 true : 1 추가 result.add(1); continue; } //포함되어있지 않으면 리스트에 false : 0 추가 result.add(0); } //result 리스트를 순회하면서 StringBuilder에 1 또는 0으로 쌓여있는 결과 출력을 위한 과정 StringBuilder sb = new StringBuilder(); for(Integer cur : result){ sb.append(cur+ " "); } System.out.println(sb.toString()); } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 12100번 : 2048(Easy) - 자바(Java) (0) 2022.06.18 [백준] 2056번 : 작업 - 자바(Java) (0) 2022.06.17 [백준] 1644번 : 소수의 연속합 - 자바(JAVA) (0) 2022.06.14 [백준] 2957번 : 이진 탐색 트리 - 자바(JAVA) (1) 2022.06.12 [백준] 23807번 : 두 단계 최단 경로3 - 자바(JAVA) (0) 2022.06.11