https://www.acmicpc.net/problem/14425
14425번: 문자열 집합
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어
www.acmicpc.net
우선 이 문제는 이진탐색(Binary_search)을 이용한 문제다.
이진탐색을 아직 잘 모른다면 https://solution-is-here.tistory.com/110
[자료구조] 이진탐색(Binary Search) 파이썬으로 마스터 하기 & 백준 10815번: 숫자카드 (파이썬,Python3)
이진탐색은 오름차순으로 정렬된 배열에서 원하는 숫자(Target)를 찾는 정렬 알고리즘입니다. 시간 복잡도는 항상 입니다. 그러므로 시간을 단축할 때 유용하게 사용할 수 있는 알고리즘입니다.
solution-is-here.tistory.com
위 링크를 보고 오면 이해할 수 있다!
문제를 보고 필요한 정보를 습득하는 능력을 길러야 한다.
우선 위 문제를 보면 N개의 문자열, M개의 문자열, 집합 S에 포함되어 있는 것 이렇게 3개를 파악해야 한다.
이렇게 파악을 한 다음에 입력을 봐야 한다.
입력에서는 N개의 줄에 집합 S에 포함되어 있는 문자열들이 주어진다고 한다.
다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다고 했다.
입력까지 파악을 완료했다면 출력을 봐야 한다.
출력이 가장 중요한 부분이라고 할 수 있다. 첫째 줄에 M개의 문자열중 몇 개가 S포함 되어 있는지 출력한다.
즉 N개의 문자열이 있는 집합 S에 M개의 문자열 몇개가 있는지 확인해서 출력하는 문제다.
코드를 보면서 설명하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
input_ch = []
search_ch = []
for i in range(n):
a = input()
input_ch.append(a)
for i in range(m):
a = input()
search_ch.append(a)
input_ch.sort()
|
cs |
위 코드는 집합 S와 M개의 문자열을 입력받은 뒤, 집합 S를 오름차순으로 정리하는 코드다.
이진탐색을 하기 위해서는 데이터를 가지고 있는 집합은 무조건! 오름차순으로 정리되어야 한다.
|
1
2
3
4
5
6
7
8
9
10
|
def binary_search(start,end,data,target):
while start <= end:
mid = (start + end)//2
if target == data[mid]:
return 1
elif target > data[mid]:
start = mid + 1
else:
end = mid - 1
return 0
|
cs |
Binary_search 즉 이진탐색을 하는 함수다.
매개변수로 시작값(start), 끝값(end), 데이터(data), 찾는 값(target)을 받는다.
그런 다음 while반복문을 이용해서 시작값이 끝값보다 큰 경우는 고려하지 않게 설정했다.
다음 줄에 있는 코드부터는 이진 탐색을 이용한 코드이므로 이해가 가질 않는다면 맨 위에 있는 링크를 보고 와야 한다.
|
1
2
3
4
5
6
|
result = 0
for i in range(m):
if binary_search(0,n-1,input_ch,search_ch[i]) == 1:
result += 1
print(result)
|
cs |
그다음 result라는 변수를 만들어서 이진 탐색후 나온 결과값이 1(문자가 존재하는 경우)이면 1을 더하고 0(문자가 없는 경우)면 아무것도 변하지 않게 한다.
그 다음 result변수를 출력하면 문제가 해결된다.
정답코드:
|
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
|
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
input_ch = []
search_ch = []
for i in range(n):
a = input()
input_ch.append(a)
for i in range(m):
a = input()
search_ch.append(a)
input_ch.sort()
def binary_search(start,end,data,target):
while start <= end:
mid = (start + end)//2
if target == data[mid]:
return 1
elif target > data[mid]:
start = mid + 1
else:
end = mid - 1
return 0
result = 0
for i in range(m):
if binary_search(0,n-1,input_ch,search_ch[i]) == 1:
result += 1
print(result)
|
cs |