Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 슬라이딩 윈도우
- 해시 테이블
- 트리
- 에라토스테네스의 체
- 애드 혹
- boj
- 그리디
- 13164
- DP
- Python
- SSAFY
- 싸피
- 모던 JavaScript 튜토리얼
- DFS
- 수학
- 구현
- 브루트포스
- 그래프
- BFS
- 정렬
- 플로이드-워셜
- JavaScript
- 맵
- 세그먼트 트리
- 문자열
- 누적 합
- 이분 탐색
- 투 포인터
- 정수론
- 2357
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 14426 - 접두사 찾기 (Python) 본문
아이디어 #1
트라이를 이용하여 접두사인 문자열의 개수를 센다.
풀이 #1
예전에 for문으로 접두사를 찾는 코드를 PyPy3로 제출해서 통과했었는데 재채점 후 시간 초과가 되어 다시 풀어보았다.
클래스로 구현한 트라이 trie를 생성하여 insert로 문자열들을 트라이에 넣고, search로 접두사 여부를 판단한다.
트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다.
insert 메서드는 문자열의 문자들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성한다.
search 메서드는 문자열의 문자들을 루트 노드에서부터 차례로 찾고, 문자열이 존재하면 1, 그렇지 않으면 0을 반환한다.
import sys
input = sys.stdin.readline
class Trie:
def __init__(self):
self.root = dict()
def insert(self, S):
node = self.root
for c in S:
if c not in node:
node[c] = dict()
node = node[c]
def search(self, S):
node = self.root
for c in S:
if c in node:
node = node[c]
else:
return 0
return 1
N, M = map(int, input().split())
trie = Trie()
res = 0
for _ in range(N):
S = input().rstrip()
trie.insert(S)
for _ in range(M):
S = input().rstrip()
res += trie.search(S)
print(res)
아이디어 #2
bisect 모듈을 이용하여 이분 탐색으로 접두사로 포함되는 문자열을 찾는다.
풀이 #2
N개의 문자열들을 오름차순 정렬하여 리스트 S에 저장한다.
bisect_left 함수로 S에서 검사할 문자열이 삽입될 수 있는 인덱스를 찾고,
해당 인덱스에 존재하는 문자열의 접두사로 포함되면 결과값 res를 1 증가시킨다.
import sys
from bisect import bisect_left
input = sys.stdin.readline
N, M = map(int, input().split())
S = sorted([input().rstrip() for _ in range(N)])
res = 0
for _ in range(M):
temp = input().rstrip()
idx = bisect_left(S, temp)
if idx < N and S[idx].startswith(temp):
res += 1
print(res)
'알고리즘' 카테고리의 다른 글
[BOJ] 6549 - 히스토그램에서 가장 큰 직사각형 (Python) (0) | 2023.02.19 |
---|---|
[BOJ] 5670 - 휴대폰 자판 (Python) (0) | 2023.02.18 |
[BOJ] 11505 - 구간 곱 구하기 (Python) (0) | 2023.02.17 |
[BOJ] 19598 - 최소 회의실 개수 (Python, JavaScript) (0) | 2023.02.17 |
[BOJ] 2565 - 전깃줄 (Python) (0) | 2023.02.16 |
Comments