[프로그래머스][C++] 숫자 짝꿍

숫자 짝꿍

문제 링크

숫자 짝꿍

분석

문자열 X와 Y에서 공통된 숫자를 찾아 가장 큰 수를 만드는 문제입니다.

X와 Y에서 각 숫자가 나온 횟수를 세어줍니다.
가장 적게 나온 횟수가 짝을 이룰 수 있는 개수입니다.

숫자를 내림차순으로 짝을 정렬하면 가장 큰 수를 만들 수 있습니다.

숫자의 짝이 없는 경우 -1을 반환합니다. 숫자의 짝이 0으로만 이루어져있는 경우 0을 반환합니다.

풀이

#include <string>

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    // 각 문자열에서 숫자가 나온 횟수를 저장할 배열
    int xArray[10] { 0 };
    int yArray[10] { 0 };
    
    // 문자열 X에서 각 숫자가 나온 개수 세기
    for(int i = 0; i < X.length(); ++i)
    {
        int xInt = X[i] - '0';
        ++xArray[xInt];
    }
    
    // 문자열 Y에서 각 숫자가 나온 개수 세기
    for(int i = 0; i < Y.length(); ++i)
    {
        int yInt = Y[i] - '0';
        ++yArray[yInt];
    }
    
    // 내림차순으로 만들어야 하므로, 9부터 0까지 내려가면서 가장 큰 숫자부터 추가
    for(int i = 9; i >= 0; --i)
    {
        // i번째 숫자가 X 또는 Y에 없는 경우
        if (xArray[i] == 0 || yArray[i] == 0)
        {
            continue;
        }
        

        int minValue = (xArray[i] < yArray[i]) ? xArray[i] : yArray[i];
        
        // i가 짝으로 등장한 개수만큼 추가
        for (int j = 0; j < minValue; ++j)
        {
            answer.push_back('0' + i);
        }
    }
    
    // 결과가 비어있다면 짝을 만들 수 없었다는 의미이므로 -1
    if (answer.size() == 0)
    {
        answer = "-1";
    }
    // 가장 큰 값이 0이라는 의미이므로 0
    else if (answer[0] == '0')
    {
        answer = '0';
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n + m)$입니다.

• X배열에서 숫자가 등장하는 횟수를 구하는 반복문 $O(n)$
• Y배열에서 숫자가 등장하는 횟수를 구하는 반복문 $O(m)$
• 내림차순으로 순회하는 반복문 $O(10) \approx O(1)$
• X와 Y에서 공통 부분 중 작은 값을 사용하므로 $O(min(n,m))$
• $O(n) + O(m) + O(1) + O(min(n,m))$

공간 복잡도는 $O(min(n,m))$입니다.

• X와 Y배열에서 숫자가 나온 횟수를 저장할 배열 $O(10) \approx O(1)$
• 정답을 반환하는 문자열에서 공통 부분 중 작은 크기만큼 추가적인 문자열이 생기므로 $O(min(n,m))$

테스트 1 〉 통과 (0.01ms, 3.63MB)
테스트 2 〉 통과 (0.02ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.12MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.22MB)
테스트 7 〉 통과 (0.01ms, 4.18MB)
테스트 8 〉 통과 (0.02ms, 4.16MB)
테스트 9 〉 통과 (0.01ms, 4.17MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (15.12ms, 28.9MB)
테스트 12 〉 통과 (14.95ms, 29MB)
테스트 13 〉 통과 (15.53ms, 29MB)
테스트 14 〉 통과 (14.88ms, 29MB)
테스트 15 〉 통과 (15.45ms, 29MB)
테스트 16 〉 통과 (0.01ms, 4.22MB)
테스트 17 〉 통과 (0.01ms, 4.28MB)
테스트 18 〉 통과 (0.01ms, 4.21MB)
테스트 19 〉 통과 (0.01ms, 4.21MB)