반응형
문제 출처 :
https://www.acmicpc.net/problem/3022
알고리즘 분석 :
문제 해결에 필요한 사항
1. map STL
map을 이용하여 문제를 쉽게 풀 수 있다.
예제 입력처럼
a
b
b
b -> 혼남
가 들어올 때 a가 들어오고 b가 들어오고 상관이 없지만,
b가 한번더 들어올 때 혼날지 판단 후 b의 개수를 증가시키기에 2번째 b에서는 혼나지 않는다.
결국 마지막에 b가 한번 더 들어올때 b는 혼나게 되는 것이다.
이 과정을 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 | #include <iostream> #include <cstdio> #include <map> #include <string> using namespace std; map<string, int> mp; int main() { int n; scanf("%d", &n); int ans = 0; for (int i = 0; i < n; i++) { string str; cin >> str; if (!i) mp[str]++; else { int other = 0; for (auto it = mp.begin(); it != mp.end(); it++) if (it->first != str) other += it->second; if (mp[str] > other) ans++; mp[str]++; } } printf("%d", ans); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[2367번] 파티 (0) | 2017.11.10 |
---|---|
[14715번] 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) (0) | 2017.11.10 |
[14891번] 톱니바퀴 (0) | 2017.11.09 |
[5558번] 치~즈 (0) | 2017.10.25 |
[3186번] 소변기 (0) | 2017.10.25 |