오늘의 공부

programmers.co.kr/learn/courses/30/lessons/60060

해당 코드로는 정확성은 전부 맞지만 효율성 테스트에서 1,2,3을 통과하지 못했다.

무슨 문제인지 검색해보니 선형 탐색의 방식으로는 1,2,3을 통과할 수 없다고 한다.

Tries 구조를 공부해야 풀 수 있는 문제 였다. 

아래는 내가 풀어서 효율성 테스트를 통과하지 못한 코드

int FindMatch(string& words, string& queries, int dir)
{
	int words_size = words.size();
	int queries_size = queries.size();

	if (words_size != queries_size)
		return 0;
        
	switch (dir)
	{
	case 0:
		// 뒤에서부터
		for (int i = words_size - 1; i >= 0; --i)
		{
			if (queries[i] != '?') {
				if (words[i] == queries[i])
					continue;
				else
					return 0;
			}
			else
				return 1;
		}
		break;
	case 1:
		// 앞에서부터
		for (int i = 0; i < words_size; ++i)
		{
			if (queries[i] != '?') {
				if (words[i] == queries[i])
					continue;
				else
					return 0;
			}
			else
				return 1;
		}
		break;
	}
}

vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;
	int words_size = words.size();
	int queries_size = queries.size();
	int idx = 0;
	while (idx < queries_size)
	{
		int cnt = 0;
		for (int i = 0; i < words_size; ++i)
		{
			if (queries[idx][0] == '?')
				cnt += FindMatch(words[i], queries[idx], 0);
			else
				cnt += FindMatch(words[i], queries[idx], 1);
		}
		idx += 1;
		answer.push_back(cnt);
	}
	return answer;
}

이게 내가 해결한 방식이었다. 

tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

다음의 공식 해설을 보면 출제 의도에 문자열을 다룰 수 있는지 파악과 함께 트라이 자료구조 또는 이분 탐색 등 보다 효율적인 방법을 이용해 코드를 작성할 수 있는지 파악하고자 했다고 써있다.

공식적인 해설은 다음과 같다. 정확성 풀이같은 경우는 하나하나 비교해가면서 개수를 세면 되지만 효율성 풀이 같은 경우는 좀 길다.