[코드포스 Practice4] C. Ohana Cleans Up

Ohana Matsumae is trying to clean a room, which is divided up into an n by n grid of squares. Each square is initially either clean or dirty. Ohana can sweep her broom over columns of the grid. Her broom is very strange: if she sweeps over a clean square, it will become dirty, and if she sweeps over a dirty square, it will become clean. She wants to sweep some columns of the room to maximize the number of rows that are completely clean. It is not allowed to sweep over the part of the column, Ohana can only sweep the whole column.

Return the maximum number of rows that she can make completely clean.

 

Input

The first line of input will be a single integer n (1 ≤ n ≤ 100).

The next n lines will describe the state of the room. The i-th line will contain a binary string with n characters denoting the state of the i-th row of the room. The j-th character on this line is '1' if the j-th square in the i-th row is clean, and '0' if it is dirty.

 

Output

The output should be a single line containing an integer equal to a maximum possible number of rows that are completely clean.

 

---

아 이거 어떻게 하지? 고민하다가 처음에는 n이 100이라 모든 경우 다 구해볼까 싶었는데 이건 일단 미뤄뒀다. 그러다 보니깐 문자열이 같은 것들의 개수를 찾으면 되겠다 싶었다.  - (0, 1 위치가 전부 일치해야 0을 다 지워서 1을 만들 수 있음 - 오!)  

 

같은 문자열의 개수는 먼저 sorting을 한 다음 연속해서 같은 게 몇 개가 나오는지 셌다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
 
using i64 = long long;
 
int main() {
    int n;
    scanf("%d", &n);
    vector <string> v(n);
    
    for(int i = 0; i < n; i++)
        cin >> v[i];
        
    sort(v.begin(), v.end());
        
    int count = 1;
    int max = 1;
    for(int i = 0; i < n-1; i++){
        if(v[i] == v[i+1])
            count++;
        if(v[i] != v[i+1]){
            if(max < count)
                max = count;
            count = 1;
        }
    }
    if(max < count)
        max = count;
    printf("%d", max);
    
    return 0;
}

전부 다 같은 경우를 생각 안 해줘서 마지막에 한번 더 max < count를 확인했다. 

 

---

int main() {
    int n;
    scanf("%d", &n);
    
    map<string, int> m;
    
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        m[s]++;
    }
    
    int ans = 0;
    for(auto& mi : m)
        ans = max(ans, mi.second);
        
    printf("%d\n", ans);
    
    return 0;
}

map은 pair랑 같은 걸 줄 알고 보다가 m[s]++보고 헉 아니구나 싶어서 찾아봤다. 

map은 map<int, int> 이런 식으로 사용하는데 앞의 int는 key의 자료형이고 뒤의 int는 value의 자료형이다. 

얘는 자료를 저장할 때 정렬을 한다! 그리고 만약 비교 함수를 지정하고 싶다면 map<int, int, greater> 이렇게 뒤에다 적어주면 된다. 

 

출처 : http://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS9990721111

그래서 m[s]++; 이건 아마 맨 처음 value가 0으로 초기화 되었을 거라, 키 값이 s라면 그때의 value값을 1씩 증가시켜라는 뜻이다. value는 s의 출현 횟수가 됨. 

 

for (auto& mi : m)

      ans = max(ans, mi.second);

 

다음으로 map에 있는 값들의 value값을 확인하면서 큰 값을 ans에 저장한다. 

마지막으로 출력해주면 끝! 

 

map은 다음에 쓸일이 많지 않을까 싶다. 전에 코드짤 때 이런 일을 하는 게 필요했었는데 몰라서 그냥 이차원 배열 만든 적이 많았다. 아 그리고 찾아보다가 hash_map이란 걸 알았다. map이랑 비슷한데 얘는 자동으로 정렬을 하지 않는다고 한다. 다음에는 얘도 찾아봐야겠다.