2025 - 02 - 06 기록

 

0. 개요

 

프로그래머스 문제인 숫자 짝궁을 풀어보면서 시간 초과가 나와서 고민하다가 해결 했었다.

 

 

1. 문제 내용

 

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다).  X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다. 예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.) 두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요. 제한사항 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다. X, Y는 0으로 시작하지 않습니다. X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

x와 y의 정수에서 같은 숫자가 있는경우 짝을 지어주고 많약 같은숫자가 여러개일경우 이미 짝이 지어진 정수는 다른 짝을 둘 수 없다. 그리고 짝수가 없으면 -1

이라는 조건의 문제였다.

 

처음에는 x , y 문자의 char를 전부 탐색하는 방식을 해봤었다만 시간 초과가 나와서 
알아보던 결과 
사용하지 않았던 자료구조를 찾아보게 되었다.

 

 

Set	insert로 값을 넣으며 중첩되는 값이라면 추가되지않고 int의 경우는 자동 정렬 까지 되었다. (숫자중에서 5525 , 1255 처럼 중첩되는 숫자가 있단걸 알고 사용하지않았다.)
unordered_map	map처럼 키와 값으로 정해지는 공통점은 있지만 내부 구현방식 , 정렬 여부 , 시간복잡도 , 메모리 사용량 등이 다르고 보통 키의 순서가 필요 없고 빠른 접근 속도가 필요할 경우사용된다.

 

unordered_map Count ; 

for(char c : X)
{
	Count[c]++;
}

 

그렇게 배우고 unordered_map을 사용해서 숫자중에서 같은 숫자 들이 있는 경우 해당 키(숫자)의 값(int)를 추가 해주는 방식으로 숫자의 갯수가 2 이상이고 홀수면 1을 빼서 짝수로 만들어주고 짝수에서 2로 나눈 값만큼 숫자를 추가하려 했지만

X = "5525" 같이 X하나에 5가 중첩된다는걸 생각하고 이방법도 실패로 넘어갔다.

 

 

2. 성공했던 코드

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


//어느 순간부터 비교 ,탐색의 비율이 점점 커지는 것 같다.
//자리수는 3 ,000 , 000 으로 1개부터 7개 까지 비교 하면될것 같다. 이정도면 
// 적당한 반복문도 괜찮을 듯 하다.
// 짝꿍 찾으면 한번 정렬 해준 다음 값을 더해주면 될 거 같다.
// 시간초과가 몇개 있었다 수정

int CheckValue(int num1, int num2)
{
    int N = 0;
    if (num1 > num2)
    {
        //당장은 더좋은게 생각안나니 빠르게
        int a = num1 - num2;
        N = num1 - a;
    }
    else if (num1 < num2)
    {
        int a = num2 - num1;
        N = num2 - a;
    }
    else {
        N = num1;
    }
    return N;
}


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

    unordered_map<char, int> count1;
    unordered_map<char, int> count2;

    vector<int> Number;

    for (char c: X)
    {
        count1[c]++;
    }

    for (char c : Y)
    {
        count2[c]++;
    }

    //두문자의 값을 빼주면 어떨까 

    

    for (auto count : count1)
    {
        char c = count.first;
        //cout << c << endl;
        if (count2.find(c) != count2.end())
        {
           
            int n = CheckValue(count1[c], count2[c]);
            for (int i = 0; i < n; i++)
            {
                Number.push_back(c - '0');
            }
        }
    }

   
    

    if(!Number.empty())
{
    sort(Number.begin(), Number.end(), greater<int>());

    for (int i : Number)
    {
        answer += i + '0';
    }
    if (Number[0] == 0)
    {
        answer = '0';
    }
}
     if (Number.empty())
     {
         answer = "-1";
     }

    return answer;
}

 

1. X와 Y의 내용이 담길 unordered_map<char, int> 을 만들어줘서 해당되는 키의 값을 증가시켜줬다.

2. count1 에 있는 키가 count2에 존재하는지 확인한다.

3. 숫자가 존재할 시 숫자의 갯수를 계산해준다. (5가 3개 , 5가 2개일 경우 2개의 짝이 생성된다.)

4. 배열에 해당 숫자의 갯수 만큼 숫자를 넣어준다

5. 배열이 비어있지 않다면 정렬 해주고 + '0'를 해줘서 정수를 char로 바꿔주고 정렬해도 맨앞이 0일경우 answer를 0으로 

    만약 배열이 비어있다면 answer = "-1"로 ('-1'로하면 다른 값) 바꿔 준다.

 

분명 x와 y의 char 를 일일히 탐색했을때는 포문을 2개만 사용해도 되었던 것같은데 이번에는 포문이 많고 심지어 2중 포문도 있다 그런데도  시간 초과가 나오지 않았다 

 

처음 벡터와 벡터를 탐색했을때는

O(N*M)의 시간복잡도를 가졌고

 

unrodered_map의 탐색은 O(1) 로 되어있으니

2개의 맵을 만들었으니 O(N) + O(M) 

그리고 숫자의 종류가 0~ 9 사이로 이중 포문을 사용해도 조건이 있어 최대 10번 반복 하고 그 내부의 반복문도 그렇게 많은 반복은 하지 않았을 것이라 그런것 같다.