Programmers / 숫자 짝꿍 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 숫자 짝꿍 (1단계)

문제 사이트: 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 = "";
    int zero_count = 0;

    for (char c : X) {
        int idx = 0;
        idx = Y.find(c);
        if (idx > -1) {
            answer.push_back(Y[idx]);
            Y.erase(idx, 1);
        }
        else if (idx == -1)
            continue;
    }
    
    if (answer.empty()) {
        answer += "-1";
        return answer;
    }

    zero_count = count(answer.begin(), answer.end(), '0');

    if (zero_count == answer.size()) {
        answer.clear();
        answer.push_back('0');
        return answer;
    }
    
    sort(answer.rbegin(), answer.rend());

    return answer;
}

 

처음에는 반복문을 중첩하지 않으려고 풀었는데 시간이 초과됐다. 아마도 for문제 erase가 있으니깐 시간복잡도가 O(n^2)가 된 것 같다. 그래서 erase를 사용하지 않고 푸는 방법을 생각했다.

 

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

string solution(string X, string Y) {
    string answer = "";
    int x[10] = {0};
    int y[10] = {0};

    for (int i = 0; i < X.size(); i++) {
        x[X[i] - '0']++;
    }

    for (int i = 0; i < Y.size(); i++) {
        y[Y[i] - '0']++;
    }

    for (int i = 9; i >= 0; i--) {
        int n = min(x[i], y[i]);
        for (int j = 0; j < n; j++)
            answer += to_string(i);
    }

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

    return answer;
}

 

시간 복잡도를 줄이니깐 답이 나왔다!

---

※ 알아야 할 것

 

erase, insert 메소드는 시간 복잡도가 O(N)이 된다. for에서 사용하면 중첩 for와 같은 일이 발생하니깐 조심해서 써야한다.

만약 틀린 내용이 있으면 답글 달아주세요!