반응형

문제 출처 :


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