RUBY

[백준] 문자열 집합 본문

PS/BOJ

[백준] 문자열 집합

RUBY_루비 2024. 2. 23. 23:00

 

출처:: https://www.acmicpc.net/problem/14425

분류:: 이진탐색 

 

1. 문제 이해 및 해결과정

 

 

 

2. 풀이방법

1) 이진탐색 

import sys
input= sys.stdin.readline

n, m = map(int, input().split())
arr = sorted(list(input().rstrip() for _ in range(n)))

def exist(x):
    l, r = 0, n-1
    while l <=r :
        m = (l + r) // 2
        if arr[m] == x:
            return True
        if arr[m] < x :
            l = m + 1
        else :
            r = m - 1
    return False

cnt = 0

for x in [input().rstrip() for _ in range(m)]:
    if exist(x):
        cnt += 1
print(cnt)

 

2) set

import sys
input= sys.stdin.readline

n, m = map(int, input().split())
st = set(input().rstrip() for _ in range(n))

cnt = 0
for x in [input().rstrip() for _ in range(m)]:
    if x in st:
       cnt += 1
print(cnt)

 

3. 오답원인

 

4. 알게된 점

 

'PS > BOJ' 카테고리의 다른 글

[백준] 구간 합 구하기 4  (0) 2024.02.23
[백준] 수 찾기  (0) 2024.02.23
[백준] 베스트셀러  (0) 2024.02.22
[백준] 나이순 정렬  (0) 2024.02.22
[백준] 좌표 압축  (0) 2024.02.22
Comments