[BOJ] 16499번: 동일한 단어 그룹화하기

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

2018.11.18 1차시도 - 틀렸습니다

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int main()

{

vector<string> groups;

int N;

cin >> N;

while (N--)

{

bool check = false;

string word;

cin >> word;

if (groups.size() == 0)

{

groups.push_back(word);

}

for (int i = 0; i < groups.size(); i++)

{

if (groups[i].size() != word.size())

{

continue;

}

for (int j = 0; j < word.size(); j++)

{

string compare = word.substr(j, 1);

if (groups[i].find(compare) == string::npos)

{

break;

}

else if (j == word.size() - 1)

{

check = true;

}

}

if (check)

{

break;

}

}

if (check == false)

{

groups.push_back(word);

}

}

cout << groups.size();

return 0;

}

언뜻 보면 틀릴 것 없는 코드이다(나도 굳게 확신을 가지고 있었음).

그러나 이 코드의 문제점은 가령 cat이 먼저 들어오고 tat가 들어왔을 경우, cat과 tat는 다른 그룹으로 묶여야 함에도 불구하고 tat의 모든 문자들이 cat에서 찾을 수 있으므로 같은 그룹으로 분류하게 된다. 이 점이 함정(나만 걸린 것 같지만,, 코쓱)이라면 함정일 수 있겠다.

---

• string에서 한 글자씩 떼어내기
  
  for (int j = 0; j < word.size(); j++)
  {
  string compare = word.substr(j, 1);
  }
  
  
• 문자열에서 문자열 찾기
  
  if (groups[i].find(compare) == string::npos)
  
  groups[i] 문자열 안에 compare 문자열이 있으면 그 문자열이 발견된 첫 번째 위치를 반환함. 만약, 문자열이 없다면 string::npos를 반환함

---

2018.11.18 2차시도 - 맞았습니다

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<string> groups;

int N;

cin >> N;

while (N--)

{

string word;

string ans = "";

cin >> word;

int dic[26] = {0};

for (int i = 0; i < word.size(); i++)

dic[word[i] - 97]++;

for (int i = 0; i < 26; i++)

if (dic[i] != 0)

{

ans.push_back(((char)(i + 97)));

ans += to_string(dic[i]);

}

if (groups.size() == 0)

groups.push_back(ans);

else

{

vector<string>::iterator iter = find(groups.begin(), groups.end(), ans);

if (iter == groups.end())

groups.push_back(ans);

}

}

cout << groups.size();

return 0;

}

방법을 바꿔버렸다. 단어가 들어오면 단어에 속한 알파벳 개수를 세서 cat이면 a1c1t1 이런 문자열을 만들어서 벡터에 집어넣는것이다. 말 그대로 그룹을 만든 것이다. 이렇게 하면 주어진 조건을 모두 만족할 수 있다.

---

• string에 char 추가하기
  
  문자열.push_back(캐릭터);