문제 설명

1. Mi 의 숫자가 N 에 존재하는지 출력하는 문제

풀이

1. 이분탐색을 사용하라고 문제 분류가 돼있지만, 더 빠른 풀이를 위해 BitSet 을 사용했다.
2. 이분탐색을 사용하면 O(MlgN + NlgN) 정렬하고 찾는 시간이고, BitSet 을 사용하면(N+M) 이다.
3. 메모리 제한도 높고, Mi 의 제한도 높지 않아서 쉽게 풀 수 있었다.
4. JAVA 로 약 680MS 로 정답이니 거의 엄청 빠른 퍼포먼스를 낼 수 있었다. (첫 제출은 790MS 정도였다. 이유는 숫자 + 문자열을 write 해줬기 때문이다. 변경된 것은 문자열로만 되게)

코드

import java.util.*;
import java.io.*;
/**
* https://www.acmicpc.net/problem/10815
* BOJ 백준온라인져지 10815 숫자 카드 풀이
*/
public class Main {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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());
BitSet bitSet = new BitSet();
for (int i = 0; i < N; i++) bitSet.set(Integer.parseInt(st.nextToken()) + 10000000);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) bw.write((bitSet.get(Integer.parseInt(st.nextToken()) + 10000000) ? "1 " : "0 "));
bw.flush();
}
}
view raw Main.java hosted with ❤ by GitHub

문제

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

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1 

1 0 0 1 1 0 0 1

출처


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2902 KMP는 왜 KMP일까? 풀이  (0) 2018.06.14
BOJ 백준온라인져지 2522 별 찍기 - 12 풀이  (0) 2018.06.13
BOJ 백준온라인져지 2446 별찍기 - 9 풀이  (0) 2018.06.12
BOJ 백준온라인져지 2475 검증수 풀이  (0) 2018.06.11
BOJ 백준온라인져지 11048 이동하기 풀이  (0) 2018.06.11

+ Recent posts

티스토리툴바