Sherlock and the Valid String (hackerrank)
알파벳 소문자로만 이루어진 문자열에서 하나의 문자를 제거하는 것 만으로 모든 알파벳의 출현 횟수를 동일하게 만들 수 있는지 여부를 YES 혹은 NO로 돌려주는 문제이다.
map
을 사용해 각 문자열 출현 횟수를 저장하고, 다시 출현 횟수가 몇변 등장하는지 저장해 직접 비교했다. 딱히 큰 사이즈의 테스트케이스는 없는지 잘 통과한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <bits/stdc++.h> using namespace std; string isValid(string s) { int ret = 1; array<string, 2> arrStr = {"NO", "YES"}; map<char, int> mapCount; map<int, int> mapNum; for(auto c : s) { if(mapCount.count(c) > 0) { mapCount.at(c)++; } else { mapCount.emplace(c,1); } } for(auto i : mapCount) { if(mapNum.count(i.second) > 0) { mapNum.at(i.second)++; } else { mapNum.emplace(i.second,1); } } if(mapNum.size() > 2) { ret = 0; } else if(2 == mapNum.size()) { if(1 != (*mapNum.begin()).second && 1 != (*mapNum.rbegin()).second) { ret = 0; } else { int n, m, o; if(1 != (*mapNum.begin()).second) { n = (*mapNum.rbegin()).first; m = (*mapNum.begin()).first; o = (*mapNum.begin()).second; } else { n = (*mapNum.begin()).first; m = (*mapNum.rbegin()).first; o = (*mapNum.rbegin()).second; } if(n - m == 1 || n == 1) { ret = 1; } else { ret = 0; } } } return arrStr.at(ret); } int main() { string s; getline(cin, s); string result = isValid(s); cout << result << "\n"; return 0; } |