[백준] 1544: 사이클 단어

문제 링크

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

접근 방식 / 풀이

문제를 읽으면서, 입력의 길이가 50이기 때문에 모든 경우의 수를 다 시도해봐도 괜찮을 것 같다는 생각이 들어 큰 고민 없이 브루트포스로 문제 풀이를 진행했다.

전체적인 흐름

입력이 이전에 입력받았던 단어와 같은 단어라면 아무 일도 일어나지 않으며, 다른 단어라면 vector<string>에 push된다. 출력은 vector의 크기이다.

find_string(string s)

같은 단어이기 위해서는 두 가지 조건이 필요하다.
1. 길이가 같아야 한다
2. 단어의 첫 번째 알파벳이 존재해야 하며, 그 뒤의 값도 모두 같아야 한다.

(1)을 위해 length를 비교해주었고,
(2)를 위해 s에서 word의 첫 자리수의 인덱스를 찾는다.

존재한다면, [s를 index부터 끝까지], [word를 첫번째부터 (s의 index부터 끝까지의 길이)만큼] 나눈 substring을 만든 뒤 이 둘이 같은 지 확인한다.

같을 경우, 나머지 부분인 [s를 index의 전까지], [word를 (s의 index부터 끝까지의 길이)의 인덱스부터 끝까지] 나눈 substring이 같은 지 확인한다.

이 두 가지 경우가 모두 맞다면 이것은 이전에 입력으로 들어온 값과 같은 단어이기에 vector<string>에 push하지 않는다.

현재 vector에 존재하는 모든 string에 대해 해당 작업을 반복한다.

---

답안 코드 링크 (Github)

Solution Github Link

정답 코드 (C++)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string>	word;

void	fastio(void);
void	find_string(string s);

int main(void)
{
    int	num;
	string	tmp;
	
	fastio();
	cin >> num;
	for (int i = 0; i < num; i++)
	{
		cin >> tmp;
		find_string(tmp);
	}
	cout << word.size() << "\n";
	return (0);
}

void	find_string(string s)
{
	int	vec_size = word.size();
	int	str_size = s.length();

	for (int i = 0; i < vec_size; i++)
	{
		if (word[i].length() == str_size)
		{
			int idx = s.find(word[i][0]);
			while (idx != string::npos)
			{
				if (s.substr(idx) == word[i].substr(0, str_size - idx))
				{
					if (s.substr(0, idx) == word[i].substr(str_size - idx))
						return ;
				}
				idx = s.find(word[i][0], idx + 1);
			}
		}
	}
	word.push_back(s);
}

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