14425번: 문자열 집합
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어
www.acmicpc.net
☕Language: Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int num1 = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
String[] sArr1 = new String[num1];
for (int i = 0; i < num1; i++) {
sArr1[i] = br.readLine();
}
int cnt = 0;
for (int i = 0; i < num2; i++) {
cnt += check(sArr1, br.readLine());
}
bw.write(cnt + "");
bw.flush();
bw.close();
}
public static int check(String[] sArr1, String s) {
int cnt = 0;
for (int i = 0; i < sArr1.length; i++) {
if (sArr1[i].equals(s)) {
cnt++;
}
}
return cnt;
}
}
|
🤔 해설
1. M개의 문자열
- String 배열에 저장
2. 집합 S
- 집합 S를 위한 배열을 생성하지 않고, 입력마다 check()을 호출하여 M개의 문자열과 같은 단어인지 확인
😮 이 외의 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int num1 = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < num1; i++) {
map.put(br.readLine(), 0);
}
int cnt = 0;
for (int i = 0; i < num2; i++) {
if(map.containsKey(br.readLine())) {
cnt++;
}
}
bw.write(cnt + "");
bw.flush();
bw.close();
}
}
|
1. HashMap
- Map에 M개의 문자열 저장
2. containsKey()
- 집합 S의 값을 HashMap의 Key값과 비교
🤓 집합과 맵으로 분류된 문제인데, 속도 차이가 6배정도 난다..!
- 제출번호 64906951: check() 사용
- 제출번호 64907853: HashMap<>() 사용
⭐ Hash Table은 검색, 삽입, 삭제가 모두 평균적으로 1의 시간 복잡도를 갖을 정도로 빠름
🔗 소스 코드
HJ0216/TIL/BOJ
📚 참고 자료
[백준] 14425번 : 문자열 집합 – JAVA [자바]
https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다
propercoding.tistory.com
'Computer > Algorithm_Java' 카테고리의 다른 글
| [BaekJoon] 10816번 숫자 카드 2 문제풀이 (Success) (0) | 2023.08.13 |
|---|---|
| [BaekJoon] 7785번 회사에 있는 사람 문제풀이 (Success) (0) | 2023.08.12 |
| [BaekJoon] 10815번 숫자 카드 문제풀이 (Success) (0) | 2023.08.10 |
| [BaekJoon] 1735번 분수 합 문제풀이 (Success) (0) | 2023.08.09 |
| [BaekJoon] 11651번 좌표 정렬하기 2 문제풀이 (Success) (0) | 2023.08.08 |
