숫자 짝꿍

https://school.programmers.co.kr/learn/courses/30/lessons/131128

 

 

*초기 작성 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string X, string Y) 
{
    string answer = "";
    char target;
    
    sort(X.begin(), X.end(), greater<>());
    sort(Y.begin(), Y.end(), greater<>());
    
    for(int i = 0; i < X.length();)
    {
        target = X[i];
        
        int X_cnt = count(X.begin(), X.end(), target);
        int Y_cnt = count(Y.begin(), Y.end(), target);
        
        int min_cnt = min(X_cnt, Y_cnt);
        
        answer.append(min_cnt, target);
        i += X_cnt;
    }
    
    if(answer.empty()) return "-1";
    if(answer[0] =='0') return "0";
    
    return answer;
}

• 미리 X와 Y를 내림차순으로 정렬
• X의 길이만큼 루프를 돌면서 X의 값 중 큰 값 부터 target에 넣어 카운팅
• 작은 값이 공통으로 가지고 있는 개수를 의미함으로 그 개수만큼 answer에 target 추가

이와 같은 방식으로 구현하였는데, for문 안에서 count 메서드로 루프를 또 돌기 때문에 O(n*2)의 시간복잡도를 가지게되어주어진 문자열 X와 Y의 길이가 길수록 성능 저하가 우려되었다. 

그래서 메인으로 작업하는 루프에서 count 메서드를 제거하고 미리 각 요소의 개수를 세는 방향으로 수정하려 했고,

unordered_map 컨테이너를 선택했다.

 

 

*미리 각 요소를 카운팅한 ver

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

string solution(string X, string Y)
{
    string answer = "";
    char target;

    sort(X.begin(), X.end(), greater<>());
	
    // 에러 발생
    unordered_map<char, int> X_cnt(X.begin(), X.end());
    unordered_map<char, int> Y_cnt(Y.begin(), Y.end());

    for (int i = 0; i < X.length();)
    {
        target = X[i];

        int min_cnt = min(X_cnt[target], Y_cnt[target]);
        answer.append(min_cnt, target);

        i += X_cnt[target];
    }

    if (answer.empty()) return "-1";
    if (answer[0] == '0') return "0";

    return answer;
}

• 위와 같이 코드를 수정했는데, 오류가 발생하였다..
• vector나 다른 컨테이너를 초기화 할 때 사용하는 방식을 map에 적용해서 생긴 오류였다.

 

*최종 수정 코드

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

string solution(string X, string Y) 
{
    string answer = "";
    char target;
    
    sort(X.begin(), X.end(), greater<>());
    
    unordered_map<char, int> X_cnt;
    unordered_map<char, int> Y_cnt;
    
    for(char ch : X)
    {
        X_cnt[ch]++;
    }
    for(char ch : Y)
    {
        Y_cnt[ch]++;
    }
    
    for(int i = 0; i < X.length();)
    {
        target = X[i];
        
        int min_cnt = min(X_cnt[target], Y_cnt[target]);
        answer.append(min_cnt, target);
        
        i += X_cnt[target];
    }
    
    if(answer.empty()) return "-1";
    if(answer[0] =='0') return "0";
    
    return answer;
}

• for문을 통해 각 요소의 개수를 카운팅 해주었음.
• sort는 X나 Y 둘 중 하나만 필요하기 때문에 Y에 대한 sort는 삭제하였음

수정을 하면서 보니까 문자열 두 개 다 정렬할 필요가 없어서 하나만 정렬하도록 해주었고, 카운팅 하는 과정에서 반복문이 두 번 추가되긴 하지만 메인 루프에서 2중으로 작업되지 않기 때문에 더 속도가 빨라졌다고 볼 수 있다.