하루에 하나씩

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

시간 복잡도: O(N)

재귀를 이용해 한 문자씩 더해서 출력한다.

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

class Solution {
public:
    vector<string> answer;    
    
    void recursive(string str, string digits, int depth) {
        if(depth == digits.length()) {      //문자열의 끝에 도달하면 answer에 push해주기
            if(str != "") answer.push_back(str);
            return ;
        }
        switch(digits[depth]) {     //한 단어씩 더하면서 재귀를 돌린다.
            case '2':
                recursive(str + 'a', digits, depth + 1);
                recursive(str + 'b', digits, depth + 1);
                recursive(str + 'c', digits, depth + 1);                
                break;
            case '3':
                recursive(str + 'd', digits, depth + 1);
                recursive(str + 'e', digits, depth + 1);
                recursive(str + 'f', digits, depth + 1);
                break;
            case '4':
                recursive(str + 'g', digits, depth + 1);
                recursive(str + 'h', digits, depth + 1);
                recursive(str + 'i', digits, depth + 1);
                break;
            case '5':
                recursive(str + 'j', digits, depth + 1);
                recursive(str + 'k', digits, depth + 1);
                recursive(str + 'l', digits, depth + 1);                
                break;
            case '6':
                recursive(str + 'm', digits, depth + 1);
                recursive(str + 'n', digits, depth + 1);
                recursive(str + 'o', digits, depth + 1);                
                break;
            case '7':
                recursive(str + 'p', digits, depth + 1);
                recursive(str + 'q', digits, depth + 1);
                recursive(str + 'r', digits, depth + 1);
                recursive(str + 's', digits, depth + 1);
                break;
            case '8':
                recursive(str + 't', digits, depth + 1);
                recursive(str + 'u', digits, depth + 1);
                recursive(str + 'v', digits, depth + 1);
                break;
            case '9':
                recursive(str + 'w', digits, depth + 1);
                recursive(str + 'x', digits, depth + 1);
                recursive(str + 'y', digits, depth + 1);
                recursive(str + 'z', digits, depth + 1);
                break;
        }
        return ;
    }
    
    vector<string> letterCombinations(string digits) {
        recursive("", digits, 0);
        return answer;
    }
};

int main(void){
  return 0;
}

https://leetcode.com/problems/unique-email-addresses/

시간 복잡도: O(N)

조건 1)    '+'를 만나면 @를 만날 때 까지 문자를 무시할 수 있다.

조건 2)    '@'뒤에 있는 .은 생략하면 안된다.

조건 3)    '@'앞에 있는 .은 포함하면 안된다.(afterDot변수로 구분지음)

조건 4)    중복되는 문자열은 제거해야 한다.

#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;

class Solution {
public:
    string uniqueEmail(string str){
        string answer = "";
        bool afterDot = false;
        for(int i = 0; i < str.length(); i++){
            if(str[i] == '+'){
                while(1) {      //+를 만나면 @를 만날 때까지 넘어간다.
                    if(str[i] == '@'){
                        answer += '@';
                        afterDot = true;
                        break;
                    }
                    i++;
                }
            } else if(str[i] == '@'){   //+를 안만나고 @를 만났을 때
                afterDot = true;
                answer += '@';
            } else if(str[i] == '.') {
                if(afterDot) answer += str[i];  //@이후 .은 저장하고 이전 .은 저장하지 않는다.
            } else answer += str[i];
        }
        return answer;
    }

    int numUniqueEmails(vector<string>& emails) {
        set<string> s;
        for(int i = 0; i < emails.size(); i++)
            s.insert(uniqueEmail(emails[i]));
        return s.size();
    }
};

int main(void){
  return 0;
} 

1. 문자열 T에서 S에 있는 단어들의 개수만큼 cntAlpha에 저장한다.

2. S에 들어있는 단어들부터 cntAlpha의 개수만큼 answer에 더해준다.

3. 나머지 문자들을 answer에 더해준다.

// 791. Custom Sort String

#include<iostream>
#include<string>
using namespace std;
class Solution {
public:
    string customSortString(string S, string T) {
        string answer = "";
        int cntAlpha[26] = { 0, };
        for(int i = 0; i < T.length(); i++)     //T문자열에서 각 알파뱃의 개수를 cntAlpha배열에 저장
            cntAlpha[T[i] - 'a']++;

        for(int i = 0; i < S.length(); i++){        //S에 있는 문자를 cntAlpha에 저장된 수 만큼 더해준다.
            for(int j = 0; j < cntAlpha[S[i] - 'a']; j++)
                answer += S[i];
            cntAlpha[S[i] - 'a'] = 0;
        }

        for(int i = 0; i < 26; i++){        //남은 문자열을 더해준다.
            char c = i + 'a';
            for(int j = 0; j < cntAlpha[i]; j++)
                answer += c;
        }
        return answer;
    }
};

int main(void){
  return 0;
} 

https://leetcode.com/problems/custom-sort-string/