컴프 IamCoder 11주차

컴프 11주차 풀이입니다.
11주차의 주제는 set, map이었습니다. 저는 set의 begin/rbegin을 몰라서 얼마 전 코포를 틀렸던 경험이 있습니다. ㅠㅠ \

서로 다른 수의 개수 L

• set<int>를 선언합니다.
• 수를 입력받아 집합에 insert합니다.
• set의 크기를 출력합니다.
• 참 쉽죠?

서로 다른 단어의 개수 L

• set<string>를 선언합니다.
• 단어를 입력받아 집합에 insert합니다.
• set의 크기를 출력합니다.
• 날먹이죠?

특정 수의 개수

• map<int,int>를 선언합니다.
• 배열을 입력받아 각 원소를  key로 가지는 map의 원소의 value값을 1 더해줍니다.
• 배열을 입력받아 각 원소를 key로 가지는 map의 원소의 value값을 출력합니다.
• map은 그런 식으로 작동합니다. 정말개쩌는자료구조입니다.

부분 수열의 합

• 배열을 입력받아 누적합을 계산합니다.
• 누적합의 원소 중 어떤 수 a가 b번 나온다면, 모든 a에 대한 $(b*(b-1)/2)$의 합을 출력하면 됩니다.
• map<int,int>로 구현하면 됩니다.

경곽의 보석괴물

• D번이랑 같은데, 모든 입력에 -1을 더해 처리하면 됩니다.
• 생각해보면 자명한데, 그 생각하기가 어려워서 PS가 어렵습니다. 제가 똑떨인 이유도 그것입니다.

chemoon100의 새로운 평가 방법 2

• map<string,int>를 선언합니다.
  • 이래서 맵이 좋습니다. 위치 지정을 string이던 구조체던 아무거나 쓸 수 있습니다.
• 단어들을 입력받아 각 단어를 key로 하는 map의 원소의 value값을 1 더해줍니다.
• auto로 map의 모든 원소를 불러와, 정한 개수보다 많이 나오는 것의 수를 세 출력합니다.

chemoon100의 새로운 평가 방법

map<string,int>를 선언합니다. 단어들을 입력받아 각 단어를 key로 하는 map의 원소의 value값을 1 더해줍니다. 단어들을 입력받아 각 단어를 key로 하는 map의 원소의 value값을 출력합니다.

A 차집합 B

• set<int>를 선언합니다.
• A집합의 수를 입력받아 set에 insert합니다.
• B집합의 수를 입력받아 set에서 erase합니다.
• auto로 map의 모든 원소를 불러와 출력합니다.

A 합집합 B

• set<int>를 선언합니다.
• A집합의 수를 입력받아 set에 insert합니다.
• B집합의 수를 입력받아 set에 insert합니다.
• auto로 map의 모든 원소를 불러와 출력합니다.

수열의 합

• map<int,int>를 선언합니다.
• 첫 번째 수를 key로 하는 값의 value에 1을 저장합니다.
• 그 다음으로 오는 수에 대해 다음을 실행합니다:
• 그 전까지 map에 있던 수에 대해, map의 모든 원소의 key값을 불러와 그 원소의 value를 거기(key값)에 현재 수를 더한 값을 key로 하는 값의 value에 더합니다.
• 현재 수를 key로 하는 값의 value에 1을 더합니다.
• 즉, map의 key는 부분집합 원소의 합, value는 그 합을 가지는 부분집합의 수입니다.
• auto 등으로 모든 원소를 뽑아와, 가장 큰 value값을 찾습니다.
• 그와 같은 value값을 가지는 모든 key를 출력합니다.

라인월드 3

• set<int>를 선언합니다.
• 첫 번째 수를 set에 insert하고 저장합니다.
• 그 다음으로 오는 모든 수에 대해 다음을 실행합니다:
• 현재 수를 그 직전 수에 더합니다.
• 즉, 전체 수열의 누적합만을 고려합니다.
• 최대 크기 m에 대해, 누적합에서 m을 뺀 값 이상의 값을 set에서 lower_bound를 통해 찾습니다. lower_bound값이 x라면, 우리가 찾는 정수값은 ``*x입니다.
• 만약 set::lower_bound != set::end 라면, 현재 누적합에서 *x를 뺀 값을 저장합니다.
• 이 값은 승민이가 가질 수 있는 이익 중 하나입니다.
• 저장한 값 중 최대를 출력합니다.

문제들 중에 어려운 게 없어서 좋았습니다.

void q1(){
    long long n; cin>>n;
    set<long long>s;
    while(n--){
        long long t; cin>>t;
        s.insert(t);
    }
    cout<<s.size();
}
void q2(){
    long long n; cin>>n;
    set<string>s;
    while(n--){
        string t; cin>>t;
        s.insert(t);
    }
    cout<<s.size();
}
void q3(){
    map<long long,long long>mp; 
    long long n,m; cin>>n;
    while(n--){
        long long t; cin>>t;
        mp[t]++;
    }
    cin>>m;
    while(m--){
        long long t; cin>>t;
        cout<<mp[t]<<" ";
    }
}
void q4(){
    map<long long,long long>mp; 
    long long n; cin>>n;
    long long cur=0; mp[0]++; 
    long long ans=0;
    while(n--){
        long long t; cin>>t;
        cur+=t;
        ans+=mp[cur];
        mp[cur]++;
    }
    cout<<ans;
}
void q5(){
    map<long long,long long>mp; 
    long long n; cin>>n;
    long long cur=0; mp[0]++; 
    long long ans=0;
    string s; cin>>s;
    while(n--){
        long long t=s[n]-'0';
        cur+=t-1;
        ans+=mp[cur];
        mp[cur]++;
    }
    cout<<ans;
}
void q6(){
    long long n; cin>>n;
    map<string,long long>mp;
    while(n--){
        string s; cin>>s;
        mp[s]++;
    }
    long long m,ans=0; cin>>m;
    for(auto i:mp){
        if(i.second>=m) ans++;
    } cout<<ans;
}
void q7(){
    long long n; cin>>n;
    map<string,long long>mp;
    while(n--){
        string t; cin>>t;
        mp[t]++;
    }
    long long m; cin>>m;
    while(m--){
        string s; cin>>s;
        cout<<mp[s]<<endl;
    }
}
void q8(){
    set<long long>a; 
    long long n,m;
    cin>>n>>m;
    while(n--){
        long long t; cin>>t;
        a.insert(t);
    }
    while(m--){
        long long t; cin>>t;
        if(a.find(t)!=a.end()) 
            a.erase(t);
    }
    if(a.size()==0) 
        cout<<"-1";
    else for(auto i:a) 
    cout<<i<<" ";
}
void q9(){
    set<long long>a; 
    long long n,m;
    cin>>n>>m;
    while(n--){
        long long t; cin>>t;
        a.insert(t);
    }
    while(m--){
        long long t; cin>>t;
        a.insert(t);
    }
    for(auto i:a) 
        cout<<i<<" ";
}
void q10(){
    long long n; cin>>n;
    map<string,long long>mp;
    while(n--){
        long long a,b; string s; 
        cin>>a>>s>>b;
        if(a==1) mp[s]+=b;
        else if(mp[s]>=b){
            cout<<0<<endl; 
            mp[s]-=b;
        }
        else{
            cout<<b-mp[s]<<endl; 
            mp[s]=0;
        }
    }
}
void q11(){
    long long n,i; cin>>n;
    map<long long,long long>mp;
    for(i=0;i<n;i++){
        long long t; cin>>t;
        vector<pair<long long,long long>>v; 
        v.clear();
        for(auto j:mp) 
            v.push_back(j);
        for(auto j:v) 
            mp[j.first+t]+=j.second;
        mp[t]++;
    }
    long long mx=0;
    for(auto i:mp)
        if(i.second>mp[mx]) 
            mx=i.first;
    cout<<mp[mx]<<endl;
    for(auto i:mp)
        if(i.second==mp[mx]) 
            cout<<i.first<<" ";
}
void q12(){
    long long n,m,i; 
    cin>>n>>m;
    set<long long>cs; 
    cs.insert(0);
    long long mx=0,ccs=0,t;
    for(i=0;i<n;i++){
        cin>>t; ccs+=t;
        auto x=cs.lower_bound(ccs-m);
        if(x!=cs.end()) 
            mx=max(mx,ccs-*x);
        cs.insert(ccs);
    }
    cout<<mx;
}