[Programmers] 영어 끝말잇기

https://school.programmers.co.kr/learn/courses/30/lessons/12981

프로그래머스

 

---

 

문제 해결 과정

착안

주어진 규칙에 따라 $i = 2, 3, ..., n$에 대하여, $i$번째 사람이 성공적으로 끝말잇기를 하는지 여부를 판단한다. 이때 이미 등장한 단어인지를 확인하는 과정을 위해 해시 맵(hash map) 자료 구조를 활용하여 문자열에 대한 탐색을 빠르게 수행하고자 하였다.

 

구현

해시 맵 자료 구조를 사용하기 위하여 std::unordered_map<> 클래스 및, 해당 클래스의 [] 연산자 특성을 활용하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<string, int> wordMap;

bool decision(string prev, string next)
{
	return prev.back() == next.front() && wordMap[next] == 1;
}

vector<int> solution(int n, vector<string> words)
{
	vector<int> answer(2);
	wordMap[words[0]]++;

	for (int i = 1; i < words.size(); i++)
	{
		wordMap[words[i]]++;
		if (!decision(words[i - 1], words[i]))
		{
			answer = { i % n + 1, i / n + 1};
			break;
		}
	}

	return answer;
}

 

실행 결과