[백준/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];
}
Author And Source
이 문제에 관하여([백준/CPP/JS] 7587번. Anagrams), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/boj7587저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)