백준 14426번 Pseudo code

문제 링크

https://www.acmicpc.net/problem/14426

14426번: 접두사 찾기

 

시간 제한 / 메모리 제한

1 초

1536 MB

 

문제

문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다.

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 M개의 문자열 중에 총 몇 개가 포함되어 있는 문자열 중 적어도 하나의 접두사인지 출력한다.

예제 입력

5 10
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
star
start
code
sunday
coding
cod
online
judge
plus

예제 출력

7

 

문제 풀이를 위해 생각한 것

1. 메모리 제한이 타 문제에 비해 매우 넉넉한 편이다. 왜일까?
2. 이전에 코딩테스트에서 비슷한 문제를 완전 탐색으로 푼 경험이 있다.
3. 완전 탐색으로 풀게 되면 N*M, 즉 최악의 경우 10,000 * 10,000으로, 1초 1억 연산 공식에 따라 시간 제한에 걸릴 가능성이 있다.
4. 완탐이 아니라면?
5. 맵 자료구조를 쓸 수 있을 것 같다.
6. 집합 S에 포함된 N개의 단어를 첫번째 자리부터 마지막 자리까지 slicing하고
7. 이 문자열을 key로 맵에 'True' value를 저장한다. 맵 자료구조의 삽입 연산은 O(1)의 시간 복잡도를 갖는다.
8. 한 문자열의 길이는 최대 500이고, 최대 10,000개의 문자열이 입력되기 때문에, 최대 5,000,000회의 O(1) 연산을 수행하는 것이다.
9. 그리고 검사하는 문자열 M개를 각각 map에서 조회한 뒤, True이면 count를 +1 한다. 맵 자료구조의 조회는 O(1)의 시간복잡도를 갖는다.

 

사용한 자료구조

맵.

배열을 이용한 완전 탐색보다 시간 복잡도를 획기적으로 줄일 수 있다.

맵 자료구조의 삽입, 조회는 평균적으로 O(1)의 시간복잡도를 갖기 때문이다.

파이썬 dict(map)자료구조의 연산별 시간복잡도

 

풀이 코드

n, m = 첫 입력값을 split하여 정수로
map = 맵 자료구조 선언
cnt = 0

n번 동안:
	s = 입력값
	1부터 s의 길이 동안 i에 대하여:
		map[s[:i]] = True # 문자열 slicing

m번 동안:
	s = 입력값
	if map[s] == True:
		cnt += 1

print cnt

 

시간 복잡도 분석

O(N).

길이가 최대 500인 문자열 N개에 대하여, 문자열을 slicing해 맵에 저장한다. 500 * N * O(1). (500은 상수 시간).

맵 자료구조에서 검사하려는 문자열 M개의 value를 각각 조회한다. M * O(1).

최악의 경우 N = M.

 

따라서 최대차항의 계수를 제외한 시간 복잡도는 O(N)이다.

 

문제에서 중요한 부분

배열을 이용한 완전 탐색으로 시간 복잡도를 계산해보고, 시간 제한에 걸릴 것 같다면 다른 방법을 떠올리는 것이 중요했다.