알고리즘 - 구현

<자체 문제>

계좌번호 문제

(제한 시간 1초)

입력: 계좌번호의 array 

{1111-111-1111, 222-222-222, 3333-333,333-3333, 3333-3333} -> 갯수는 최대 200,000개 

-> 이 계좌번호가 
1. 유효한 계좌번호인지 
2. 어떤 은행의 계좌번호인지 
-> 각 은행별로 유효한 계좌번호의 갯수를 출력 

 

유효 계좌 체크
1. 계좌번호는 0~9 까지의 숫자 - 으로 이루어짐 이외의 글자 x
2. 계좌번호의 숫자는 11~14개면 유효,
3. - 의 숫자는 0~3까지 유효, 맨 앞, 맨 뒤 x, 연속이면 x
4. 숫자의 갯수와 하이픈의 갯수가 같고, 하이픈의 위치가 같아야함 = 같은 은행 


출력
3
2
1
이런식으로 내림차순 출력

 

풀이) 이문제는 직접 생각해보고 문제를 내봤다.

해당 계좌가 유효한지를 체크하고, 체크한 계좌의 은행의 count를 올려주는 문제이다.

해당 문제는 array가 최대 200,000개 이며, 계좌번호의 최대 길이는 숫자 갯수 + -의 갯수를 더하면 17이 최대이기때문에 17n으로 풀수있다.

 

어떤은행의 count를 올려줘야하는지 알아야하는데 o(1)으로 키값으로 바로 체크할 수 있게 map으로 설정하는게 핵심이다.

 

array의 배열의 갯수만큼 반복문을 돌면서, 계좌번호를 유효한 계좌인지 검사하고, 유효한 계좌번호이면 

map의 key를 string으로 map[숫자의갯수 + "-" + 하이픈갯수 + "-" + 하이픈 인덱스]의 count를 올려주면 된다.

 

하이픈 인덱스는 최대 3개까지 가능하기때문에 

숫자의갯수 + "-" + 하이픈갯수 + "-"를 기본 string으로 만들고

 

반복문을 통해서 string값을 더해주면 될것이다. 

 

마지막에 map을 iterator로 map에 있는 갯수만큼 새배열에 넣어서 count를 출력하면 될것이다.

 

코드)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<string> arr(N+1);
    
    //은행 갯수
    map<string, int> m;
    
    
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }
    
    //max = 200000
    for(int i=0; i<arr.size(); i++){
        string str = arr[i];
        
        bool isSame = true;
        int numCount = 0;
        int hyphenCount = 0;
        
        vector<int> saveIndex; 
        for(int j=0; j<str.length(); j++){
            char c = str[j];
            
            // 맨 앞, 맨 뒤 x
            if(j == 0 || j == str.length()-1){
                if(c == '-'){
                    isSame = false;
                    break;
                }
            }
            //연속이면 x
            if(j != 0 && c == str[j-1] && c == '-'){
                isSame = false;
                break;
            }
            
            //1. 계좌번호는 0~9 까지의 숫자 - 으로 이루어짐 이외의 글자 x
            if((c < '0' || c > '9') && c != '-'){
                isSame = false;
                break;
            }
            
            if(c >= '0' && c <= '9'){
                numCount++;
            }
            if(c == '-'){
                //hyphen 위치 저장 
                saveIndex.push_back(j);
                hyphenCount++;
            }
        }
    
        //2. 숫자 11~14,
        if(numCount < 11 || numCount > 14){
            isSame = false;
        }
    
        //3. - 은 0~3까지
        if(hyphenCount > 3){
            isSame = false;
        }
        
        
        if(isSame){
            //숫자의 갯수와 하이픈의 갯수가 같고, 하이픈의 위치가 같아야함 = 같은 은행   
            string temp = to_string(numCount) + "-" + to_string(hyphenCount) + "-";
            
            for(int k=0; k<saveIndex.size(); k++){
                temp += to_string(saveIndex[k]) + "-";
            }
            
            m[temp]++;
            cout << "temp: " << temp << '\n';
        }
        cout << "str: " << str << '\n';
        
    }
    
    vector<int> arr1;
    for(auto it: m){
        arr1.push_back(it.second);
    }
    
    sort(arr1.begin(), arr1.end(), greater<>());
    
    for(int i=0; i<arr1.size(); i++){
        cout << arr1[i] << "\n";
    }

    return 0;
}