(C++) - 백준(BOJ) 11608번 : Complexity

https://www.acmicpc.net/problem/11608

11608번: Complexity

greedy문제였습니다.

 

 

 

📕 풀이방법

 '최소'로 문자들을 지움으로써 알파벳의 종류가 2개 이하가 되게 하려면 말 그대로 빈도수가 많은 2종류를 제외한 나머지를 지우면 됩니다.

 

📔 입력 및 초기화

 입력을 받습니다. 입력받은 문자열에 대해 나온 알파벳의 개수를 세줍니다. 

 

📔 풀이과정

 1. 나오지 않은 알파벳은 제외하고 나온 알파벳들의 빈도 수를 vector변수에 저장합니다. 그러면서 나온 알파벳의 종류 또한 세주어 변수 cnt에 저장합니다.

 

 2. 오름차순으로 정렬합니다.

 

 3. i = 0 ~ i < cnt - 2만큼 저장된 vector변수를 확인하면서 ans변수에 값을 더해줍니다.

 

 

📔 정답출력

 빈도수가 가장 많은 두 개의 알파벳을 제외한 나머지 빈도수들을 모두 더한 값 ans를 출력합니다.

 

---

 

 

📕 Code

#include <bits/stdc++.h>
using namespace std;
string s;
int alpha[26], cnt, ans;
vector <int> v;
int main(){
    cin >> s;
    for(int i = 0; i < s.size(); i++) alpha[s[i]-'a']++;
    for(int i = 0; i < 26; i++) if(alpha[i]) v.push_back(alpha[i]),cnt++;
    sort(v.begin(), v.end());

    for(int i = 0; i < cnt - 2; i++){
        ans += v[i];
    }
    cout << ans;
}