์ฐ์ข ์ด๋ ์์ฒญ๋ ๊ธฐ์ต๋ ฅ์ ๊ฐ์ง๊ณ ์๋ค. ๊ทธ๋์ ํ๋ฃจ ๋์ ๋ณธ ์ ์๋ค์ ๋ชจ๋ ๊ธฐ์ต ํ ์ ์๋ค. ํ์ง๋ง ์ด๋ฅผ ๋ฏฟ์ ์ ์๋ ๋๊ท๋ ๊ทธ์ ๊ธฐ์ต๋ ฅ์ ์ํํด ๋ณด๊ธฐ๋ก ํ๋ค. ๋๊ท๋ ์ฐ์ข ์ ๋ฐ๋ผ ๋ค๋๋ฉฐ, ์ฐ์ข ์ด ํ๋ฃจ ๋์ ๋ณธ ์ ์๋ค์ ๋ชจ๋ โ์์ฒฉ1โ์ ์ ์ด ๋์๋ค. ๊ทธ๊ฒ์ ๋ฐํ์ผ๋ก ๊ทธ๊ฐ ์ง์ง ์๊ธฐ์์ธ์ง ์์๋ณด๊ธฐ ์ํด, ๋๊ท๋ ์ฐ์ข ์๊ฒ M๊ฐ์ ์ง๋ฌธ์ ๋์ก๋ค. ์ง๋ฌธ์ ๋ด์ฉ์ โX๋ผ๋ ์ ์๋ฅผ ์ค๋ ๋ณธ ์ ์ด ์๋๊ฐ?โ ์ด๋ค. ์ฐ์ข ์ ๋งํ์์ด ๋ชจ๋ ๋๋ต์ ํ๊ณ , ๋๊ท๋ ์ฐ์ข ์ด ๋ดค๋ค๊ณ ์ฃผ์ฅํ๋ ์ ๋ค์ โ์์ฒฉ2โ์ ์ ์ด ๋์๋ค. ์ง์ ๋์์จ ๋๊ท๋ ๋ต์ด ๋ง๋์ง ํ์ธํ๋ ค ํ์ง๋ง, ์ฐ์ข ์ ๋ฐ๋ผ๋ค๋๋๋ผ ๋๋ฌด ํ๋ค์ด์ ์ฌ๋ฌ๋ถ์๊ฒ ๋์์ ์์ฒญํ๋ค. ๋๊ท๋ฅผ ๋์์ฃผ๊ธฐ ์ํด โ์์ฒฉ2โ์ ์ ํ์๋ ์์๋๋ก, ๊ฐ๊ฐ์ ์์ ๋ํ์ฌ, โ์์ฒฉ1โ์ ์์ผ๋ฉด 1์, ์์ผ๋ฉด 0์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํด๋ณด์.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ ์คํธ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ๋ค์ด์จ๋ค. ๋ค์ ์ค์๋ โ์์ฒฉ 1โ์ ์ ์ด ๋์ ์ ์์ ๊ฐ์ N(1 โค N โค 1,000,000)์ด ์ ๋ ฅ์ผ๋ก ๋ค์ด์จ๋ค. ๊ทธ ๋ค์ ์ค์ โ์์ฒฉ 1โ์ ์ ํ ์๋ ์ ์๋ค์ด N๊ฐ ๋ค์ด์จ๋ค. ๊ทธ ๋ค์ ์ค์๋ โ์์ฒฉ 2โ์ ์ ์ด ๋์ ์ ์์ ๊ฐ์ M(1 โค M โค 1,000,000) ์ด ์ฃผ์ด์ง๊ณ , ๋ค์ ์ค์ โ์์ฒฉ 2โ์ ์ ์ด ๋์ ์ ์๋ค์ด ์ ๋ ฅ์ผ๋ก M๊ฐ ๋ค์ด์จ๋ค. ๋ชจ๋ ์ ์๋ค์ ๋ฒ์๋ int ๋ก ํ๋ค.
์ถ๋ ฅ
โ์์ฒฉ2โ์ ์ ํ์๋ M๊ฐ์ ์ซ์ ์์๋๋ก, โ์์ฒฉ1โ์ ์์ผ๋ฉด 1์, ์์ผ๋ฉด 0์ ์ถ๋ ฅํ๋ค.
๐ก ์ซ์๋ฅผ key๊ฐ์ผ๋ก ์ด์ฉ
๐ก ์ฒ์ ๋์จ ์ซ์๋ value์ true ์ ์ฅ
๐ก key ๊ฐ์ด ์์ผ๋ฉด 1 ์ถ๋ ฅ, ์๋๋ฉด 0 ์ถ๋ ฅ
1) ์ฒ์ ๋์จ ์ซ์๋ value์ true ์ ์ฅ
memo.put(num, true);
2) key ๊ฐ์ด ์์ผ๋ฉด true ์ถ๋ ฅ, ์๋๋ฉด false ์ถ๋ ฅ
if(memo.containsKey(num))
bw.write("1\n");
else
bw.write("0\n");
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
public class Hash_4 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
while(tc-->0){
HashMap<Integer,Boolean> memo = new HashMap<>();
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
for(int i=0; i<n; i++) {
int num = Integer.parseInt(s[i]);
memo.put(num, true);
}
int m = Integer.parseInt(br.readLine());
s = br.readLine().split(" ");
for(int i=0; i<m; i++) {
int num = Integer.parseInt(s[i]);
if(memo.containsKey(num))
bw.write("1\n");
else
bw.write("0\n");
}
}
bw.flush();
bw.close();
br.close();
}
}
์ฑ๊ณตโจ
StringBuilder๋ก ํ๋๋ ์ถ๋ ฅํ์์ด ์ด์ํ๋ค๊ณ ๋ฌ๋ค..
๊ทธ๋์, BufferedWriter์ ์ฌ์ฉํ๋ค.