[백준] 14426: 접두사 찾기

문제 링크

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

접근 방식 / 풀이

문자열의 길이도 500자고, 입력도 10000개가 들어온다고 해서 시간을 단축시키는 것에 대해서 고민을 했던 문제였다.
생각을 해보다가, 접두사라면 해당 단어와 첫 번째 글자는 무조건 같기 때문에 이 점을 이용해서 multimap을 사용하기로 했다.

• multimap : <key, value>로 구성되어 있다. 일반 map은 key값이 중복되면 안되지만, multimap은 중복되어도 된다.
  이 문제처럼 단어의 첫 글자를 key로 하는 경우, 이는 충분히 중복될 수 있는 값이기 때문에 multimap을 사용하기로 했다.

multimap의 equal_range() 함수를 이용해서, 같은 key값을 가지는 값(맨 앞 자리가 같은 단어)들 내에서만 접두사가 올바른 지 체크를 진행하였다. find() 함수의 리턴값은 해당 값을 찾았을 때 시작 인덱스를 반환하는데, 그것이 0(단어의 맨 앞)이어야 올바른 접두사라고 판단할 수 있다.
처음 작성한 코드에 이 곳에 오류가 있었는데 맞았다고 해서 테스트케이스 추가 요청을 했다...!

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드 (C++)

#include <iostream>
#include <string>
#include <map>
#include <utility>

using namespace std;

multimap<char, string> mmap;
void	fastio(void);

int main(void)
{
	string 	s;
	int	n, m, ret = 0;
	multimap<char, string>::iterator	iter;
	
	fastio();
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		mmap.insert({s[0], s});
	}
	for (int i = 0; i < m; i++)
	{
		cin >> s;
		for (iter = mmap.equal_range(s[0]).first; iter != mmap.equal_range(s[0]).second; iter++)
			if (iter->second.find(s) == 0)
			{	ret++;	break;}
	}
	cout << ret << "\n";
	return (0);
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}