[백준/JAVA] 14425번: 문자열 집합

🔺 문제

14425번: 문자열 집합

 

🔺 코드

- 정답 1 ) HashSet 이용

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        int n = Integer.parseInt(st.nextToken());   // 집합 S
        int m = Integer.parseInt(st.nextToken());   // 검사해야 하는 문자열들
        
        Set<String> set = new HashSet<>();
        
        for(int i = 0 ; i < n ; i++) {
            set.add(br.readLine());
        }
        
        int cnt = 0;
        for(int i = 0 ; i < m ; i++) {
            String str = br.readLine();
            
            if(set.contains(str))
                cnt++;
        }
        
        System.out.println(cnt);
    }
}

✅ 해결 아이디어
- HashSet 사용해서 집합 S에 문자열 추가
- Set이 입력받은 값을 갖고 있으면 (contains) 카운트

 

 

- 정답 2 ) 트라이 이용

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());   // 집합 S
        int M = Integer.parseInt(st.nextToken());   // 검사할 문자열들
        
        // 1) 트라이 자료구조 구축
        Node root = new Node();
        while(N --> 0) {
            char[] chArr = br.readLine().toCharArray(); // 집합 S의 문자열
            Node now = root;
            
            for(int i = 0 ; i < chArr.length ; i++) {
                // 다음 노드가 공백이라면 신규 노드 생성
                if(now.next[chArr[i] - 'a'] == null) {
                    now.next[chArr[i] - 'a'] = new Node();
                }
                
                now = now.next[chArr[i] - 'a'];
                if(i == chArr.length - 1) {
                    now.isEnd = true;
                }
            }
        }
        
        // 2) 트라이 자료구조 검색
        int cnt = 0;
        while(M --> 0) {
            char[] chArr = br.readLine().toCharArray(); // 검색 문자열
            Node now = root;
            
            for(int i = 0 ; i < chArr.length ; i++) {
                // 다음 노드가 공백이라면 문자열 검색 종료
                if(now.next[chArr[i] - 'a'] == null) {
                    break;
                }
                
                now = now.next[chArr[i] - 'a']; // 현재 노드를 변수 노드로 변경
                // 문자열의 끝이고, 현재까지 모두 일치하면 문자열 일치
                if(i == chArr.length - 1 && now.isEnd) {
                    cnt++;
                }
            }            
        }
        
        System.out.println(cnt);
    }
}
 
// 트라이 자료구조 클래스
class Node {
    Node[] next = new Node[26]; // 다른 노드 배열 (size : 26)
    boolean isEnd;              // 문자열의 마지막인지 여부
}
 

 

 

---

🔺 다른 풀이들

[백준] 14425번 : 문자열 집합 – JAVA [자바]

Map - containsKey 를 사용하셨다.

(Map이랑 Set 둘다 containsKey / contains 할 때 시간 복잡도는 O(1)이라고 함)

---

💬 느낀 점

나는 해시 맵이 좋아....

 

 

1회독	2회독	3회독	4회독	5회독
V	6/28

 

(+6/28 2회독)

1차 시도 때 코드와 거의 비슷한데, TreeSet 이용했다.

TreeSet이 중복 허용도 하지 않고, default로 오름차순 정렬도 해준다구...!

(참고 : 참고 링크1, 참고 링크2, 참고 링크 3)

import java.util.*;
import java.io.*;
 
public class Main {    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());   // 집합 S
        int M = Integer.parseInt(st.nextToken());   // 검사할 문자열들
        
        // TreeSet : 중복 허용 X & 오름차순 정렬까지 함 (레드 블랙 트리)
        TreeSet<String> set = new TreeSet<>();
        while(N --> 0) {
            set.add(br.readLine());
        }
        
        int cnt = 0;
        while(M --> 0) {
            String cmd = br.readLine();
            
            if(set.contains(cmd)) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}
 

---

(참고)

✔ HashMap / HashSet 시간 복잡도 비교

자바 컬렉션(Java Collection)들의 Big O (시간 복잡도, Time Complexity)