UVA 156 Ananagrams STL 애플리케이션

2242 단어
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92
몇 개의 단어를 정해서 사전순으로 출력하면 다시 배열된 단어가 존재하지 않습니다.(테스트 결과 중복된 단어는 포함되지 않음)
단어 재배열: 자모마다 나타나는 횟수는 같지만 순서가 다르다. 즉 단어의 순서에 대한 정렬이다
사고방식 분석
리셋이 등가로 전환될 수 있는지의 여부: 단어의 구성 자모는 순서와 상관없이 두 가지 해결 방향이 있다(표준화)
  • 알파벳 계수: 각 알파벳의 출현 횟수를 통계하고 일치하면 재배열을 만족시킨다
  • map, int>dict; //            ->    
    
  • 통일 정렬: 모두 승차순으로 배열하고 같은 서열을 얻으면 재배열을 만족시킨다
  • map dict; //      ->    
    

    따라서 표준화된 단어(전체 소문자로 전환) 후에 서로 다른 사고방식에 따라 횟수를 통계하고 해당하는 옛 단어를 기록할 수 있다
  • 정의set ans; 저장 출력 결과, 자동 사전 순서대로 배열
  • 모든 표준화된 단어를 옮겨다니며, 만약 그 출현 횟수가 1이면ans 집합에 삽입하고, 마지막에 출력하면 된다
    AC 코드(C++11, 맵 표준화, 순서 무관)
    일괄 정렬#include using namespace std; map dict; // -> map trans; // -> set ans; // , string s, st; int main() { while (cin >>s && s!= "#") { st = s; for (auto& ch : st) // if (ch >= 'A' && ch <= 'Z') ch = tolower(ch); // sort(st.begin(), st.end()); // , dict[st]++; // trans[st] = s; // } for (auto p : dict) if (p.second == 1) ans.insert(trans[p.first]); // 1 for (auto& p : ans) cout <
    문자 개수#include using namespace std; map, int>dict; // -> map, string> trans; // -> set ans; // , string s, st; int main() { while (cin >>s && s!= "#") { st = s; map mp; for (auto& ch : st) { if (ch >= 'A' && ch <= 'Z') ch = tolower(ch); // mp[ch] ++; // } dict[mp]++; // trans[mp] = s; // } for (auto p : dict) if (p.second == 1) ans.insert(trans[p.first]); // 1 for (auto& p : ans) cout <

    좋은 웹페이지 즐겨찾기