[SWEA] 4261번 빠른 휴대전화 키패드

4261번 빠른 휴대전화 키패드

문제 링크

 

해결방법

처음에는 모든 경우를 다해보는 문제인줄 알았으나, 그냥 단순히 일치여부를 확인하는 문제였다

 

 

⭐️ 솔루션 ⭐️

입력받은 단어를 반복문으로 돌며, 문제의 조건과 일치하는지 확인해야한다

• S의 길이와 단어의 길이가 다르다면 이 경우는 제외한다
• 이제 단어의 알파벳 하나씩 확인을 하여 일치여부를 파악한다

 

시간 복잡도

모든 단어를 반복문으로 돌며 탐색한다 (1000)

각 단어의 모든 요소와 키패드의 일치 여부를 탐색한다 (4 * 1000)

따라서 O(4 * 1000 * 1000) 의 시간복잡도를 가진다

 

 

소스코드

문제 해결 시간 : 1h

메모리 : 14744 KB

시간 : 72 ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

char keypad[8][4] = {
    {'a','b','c','0'},{'d','e','f','0'},
    {'g','h','i','0'},{'j','k','l','0'},{'m','n','o','0'},
    {'p','q','r','s'},{'t','u','v','0'},{'w','x','y','z'}
};

int testcase;
int n,ans;
string s,in;
vector<string> word;

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        cin >> s >> n;
        
        for(int i=0; i<n; i++){
            cin >> in;
            word.push_back(in);
        }
        
        ans = 0;
        for(int i=0; i<word.size(); i++){
            if(word[i].size() != s.size()) continue;
            
            bool flag = true;
            
            for(int j=0; j<word[i].size(); j++){
                int ind = s[j] - '0' - 2;
                char ch = word[i][j];
                
                bool chk = false;
                for(int k=0; k<4; k++){
                    if(keypad[ind][k] == '0') continue;
                    
                    if(keypad[ind][k] == ch){
                        chk = true;
                        break;
                    }
                }
                
                if(!chk){
                    flag = false;
                    break;
                }
            }
            
            if(flag) ans++;
        }
        
        cout << "#" << t << " " << ans << "\n";
        
    }
    
    return 0;
}