문자열 알고리즘 문제

최중혁·2022년 5월 28일
0

알고리즘 개요

주어진 문자열을 이용해 필요한 답을 추출,

  • 문자열 처리 메소드 파악이 필수

    • sort
    • substr: 문자열 자르기 ⇒ substr(i,3) : i번째부터 길이 3까지의 문자열을 잘라서 리턴함
    • to_string: 숫자를 문자열로 변환 ⇒ to_string(10) : “10”;
    • stoi() : 문자열을 int형으로 변환 ⇒ int m = stoi(’9’); m=9;
  • 시간 복잡도가 초과할 가능성이 큼

  • char, string

string s 일때, s[i] ⇒ char, s.substr(i,0) ⇒ string

char는 s.push_back(c); or s+=c; 가능

string은 s+=s; 해야 가능

예제

2019 카카오 겨울 인턴쉽

튜플

2021 카카오 채용 연계쉽

숫자 문자열과 영단어

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    string ans="";
    int temp=0;
    int i=0;
    while(i<s.size()){
        if(s[i]>='0' && s[i]<='9'){
            ans.push_back(s[i]);
        }
        else if(s[i]=='z'){
            ans.push_back('0');
            i+=3;
        }
        else if(s[i]=='o'){
            ans.push_back('1');
            i+=2;
        }
        else if(s[i]=='t'){
            if(s.substr(i,3)=="two"){
                ans.push_back('2');
                i+=2;
            }
            else if(s.substr(i,5)=="three"){
                ans.push_back('3');
                i+=4;
            }
        }
        else if(s[i]=='f'){
            if(s.substr(i,4)=="four"){
                ans.push_back('4');
                i+=3;
            }
            else if(s.substr(i,4)=="five"){
                ans.push_back('5');
                i+=3;
            }
        }
        else if(s[i]=='s'){
            if(s.substr(i,3)=="six"){
                ans.push_back('6');
                i+=2;
            }
            else if(s.substr(i,5)=="seven"){
                ans.push_back('7');
                i+=4;
            }
        }
        else if(s[i]=='e'){
            ans.push_back('8');
            i+=4;
        }
        else if(s[i]=='n'){
            ans.push_back('9');
            i+=3;
        }
        i+=1;
    }
    answer=stoi(ans);
    return answer;
}

2020 카카오 인턴쉽 - 수식 최대화

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long func(char oper, long long a, long long b){
    if(oper=='+') return a+b;
    else if(oper=='-') return a-b;
    else if(oper=='*') return a*b;
}

long long solution(string expression) {
    long long answer = 0;
    
    vector<long long> vl;
    vector<char> vc;
    string s="";
    for(int i=0;i<expression.size();i++){
        long long num;
        if(expression[i]>='0' && expression[i]<='9'){
            s+=expression[i];
        }
        else {
            vc.push_back(expression[i]);
            num=stoll(s);
            vl.push_back(num);
            s="";
        }
        
    }
    vl.push_back(stoll(s));
    vector<string> oper_str={"*-+","*+-","+-*","+*-","-+*","-*+"};
    for(int k=0;k<oper_str.size();k++){
        vector<long long> temp_vl=vl;
        vector<char> temp_vc=vc;
        string c_str=oper_str[k];
        for(int i=0;i<c_str.size();i++){
            for(int j=0;j<temp_vl.size()-1;j++){
                if(temp_vc[j]==c_str[i]){
                    long long new_l=func(temp_vc[j],temp_vl[j],temp_vl[j+1]);
                    //return new_l;
                    temp_vl.erase(temp_vl.begin()+j);
                    temp_vl.erase(temp_vl.begin()+j);
                    temp_vl.insert(temp_vl.begin()+j,new_l);  
                    //temp_vl.erase(temp_vl.begin()+j);
                    temp_vc.erase(temp_vc.begin()+j);
                    j--;
                }
                //else j++;
            }
            
        }
        if(answer < abs(temp_vl[0])) answer=abs(temp_vl[0]);
    }
        

    return answer;
}

2018 kakao recruitment

0개의 댓글