[백준/CPP/JS] 7587번. Anagrams

[백준] 7587번. Anagrams

1. 문제

Two words are anagrams if they contain the same letters but in a different order. For example ant and tan are anagrams, but ant and ton are not.

In this problem you will be supplied with a list of words. All you have to do is to pick out the word with the most anagrams and report how many anagrams it has.

2. 입력

Input consists of a number of lists. Each list begins with a number, n, which is the number of words in the list (0 < n <= 1000). The last line of input contains the number 0 – this marks the end of input and should not be processed. Each list contains n words, each on a single line. All words consist of lower case letters only. No word will contain more than 8 letters. Every list will contain at least one word that has an anagram in the list.

3. 출력

Output consists of one word from each list, the word with the most anagrams within the list, followed by a space, followed by the number of anagrams. The word displayed will be the first occurrence in the list of the anagram. If more than one word has the same highest number of anagrams, display only the one that comes first in the list of words.

4. 풀이

• 문자열 배열을 돌면서 자기 뒤에 있는 문자와 자신이 아나그램인지 비교한다.
• 아나그램이면 count를 추가해주고 배열 끝까지 탐색이 끝났으면 count를 비교해서 최댓값을 갱신한다.
• 아나그램인지 확인하기 위해 map을 사용하였다.

bool isAnagram(map<char, int> hs, string word)
{
  for (int i = 0; i < word.size(); i++)
  {
    if (hs.find(word[i]) == hs.end())
      return false;
    hs[word[i]] -= 1;
    if (hs[word[i]] == 0)
      hs.erase(word[i]);
  }
  return true;
}

5. 처음 코드와 달라진 점

• 자바스크립트로 구현할 때는 primitive 타입이 아니면 함수에서 수정하면 해당 데이터가 수정 되기 때문에 함수에서 임시 map을 하나 만들어주었다.

6. 코드 - cpp

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

bool isAnagram(map<char, int> hs, string word)
{
  for (int i = 0; i < word.size(); i++)
  {
    if (hs.find(word[i]) == hs.end())
      return false;
    hs[word[i]] -= 1;
    if (hs[word[i]] == 0)
      hs.erase(word[i]);
  }
  return true;
}

int main()
{
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;
  string words[1000];
  while (n != 0)
  {
    string answerStr;
    int answerInt = 0;
    for (int i = 0; i < n; i++)
      cin >> words[i];

    for (int i = 0; i < n; i++)
    {
      int count = 0;
      map<char, int> hs;
      for (int j = 0; j < words[i].size(); j++)
        hs[words[i][j]] += 1;

      for (int j = i + 1; j < n; j++)
        count += isAnagram(hs, words[j]) ? 1 : 0;

      if (answerInt < count)
      {
        answerStr = words[i];
        answerInt = count;
      }
    }

    cout << answerStr << " " << answerInt << endl;
    cin >> n;
  }
}

7. 코드 - js

function isAnagram(hs, word) {
  let tempHs = new Map(hs);
  for (const x of word) {
    if (!tempHs.has(x)) return false;
    tempHs.set(x, tempHs.get(x) - 1);
    if (tempHs.get(x) == 0) tempHs.delete(x);
  }
  return true;
}

function solution(words) {
  let answerWord;
  let answerCount = 0;

  for (let i = 0; i < words.length; i++) {
    let count = 0;
    const hs = new Map();

    for (const x of words[i]) {
      hs.set(x, (hs.get(x) || 0) + 1);
    }

    for (let j = i + 1; j < words.length; j++) {
      count += isAnagram(hs, words[j]) ? 1 : 0;
    }

    if (answerCount < count) {
      answerWord = words[i];
      answerCount = count;
    }
  }

  return [answerWord, answerCount];
}