프로그래머스 문제, 숫자 짝꿍(C++)

코딩테스트 연습 - 숫자 짝꿍 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

조건

3 ≤ X, Y의 자리수 ≤ 3,000,000

X, Y는 0으로 시작하지 않음.

출력할 정수가 큰 수일 수 있으므로 string 값으로 반환

 

구상

기본 골자는 X 내의 숫자들을 모두 세고 Y에서 하나가 나올 때마다 문자열에 더한다. 이 때 나오는 문자열을 큰 수 순으로 정렬하여 반환하기로 했다.

처음 시도는 unordered_map을 활용하는 것이었다. X, Y 문자열이 길다는 생각이 들어서 시도하였고 다행히 통과할 수 있었다.

 

< 1차 시도 >

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

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    unordered_map<char,int> x_nums;
    for(auto xchar : X)
        x_nums[xchar]++;
    for(auto ychar : Y)
        if(x_nums[ychar] > 0){
            answer.push_back(ychar);
            x_nums[ychar]--;
        }
    if(!answer.empty()){
        sort(answer.begin(),answer.end(), [] (char a, char b) {return a>b;});
        if(answer.front() == '0') answer = "0";
    }
    else answer = "-1";
    return answer;
}

다 풀고 나니 다른 사람들의 풀이가 궁금해져 참고하니, 비슷한 방식으로 푼사람이 하나도 없는 듯 하였다.  그래서 과하게 풀었나 싶어 다시 생각해보니 unordered_map이 해시 테이블을 사용하는 특성상, 키가 많고 정렬할 필요가 없는 문제에서 유용하게 쓰일 것 같았다. 이 문제에서는 키 값을 정렬할 필요가 없다고 생각하였지만, 키의 범위가 0-9이기 때문에 굳이 unordered_map을 사용하는 대신 vector를 활용해도 되었다.

 

< 2차 시도 >

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

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    vector<int> x_nums(10, 0);
    for(auto xchar : X)
        x_nums[xchar-'0']++;
    for(auto ychar : Y)
        if(x_nums[ychar-'0'] > 0){
            answer.push_back(ychar);
            x_nums[ychar-'0']--;
        }
    if(!answer.empty()){
        sort(answer.begin(),answer.end(), [] (char a, char b) {return a>b;});
        if(answer.front() == '0') answer = "0";
    }
    else answer = "-1";
    return answer;
}

다른 사람의 풀이 중 sort()를 사용하지 않는 방식을 중점적으로 확인해봤다.

0 - 9는 인덱스로 충분히 접근 가능하다. 9가 X에 많은지 Y에 많은지만 안다면, 순서상 9부터 0까지 순서대로 추가할 수 있다. 때문에 이를 바탕으로 3차 시도를 해보았다.

< 3차 시도 >

#include <string>
#include <vector>

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    vector<int> x_nums(10, 0);
    vector<int> y_nums(10, 0);
    for(auto xchar : X)
        x_nums[xchar-'0']++;
    for(auto ychar : Y)
        y_nums[ychar-'0']++;
    
    for(int i = 9;i>=0;i--){
        int cur = (x_nums[i] > y_nums[i]) ? y_nums[i] : x_nums[i];
        for(int j = 0; j<cur; j++) answer.push_back('0'+i);
    }
    if(answer.empty()) answer = "-1";
    else if(answer[0]=='0') answer = "0";
    return answer;
}

결과

1차 시도	2차 시도	3차 시도

 

0과 9까지 크기에 따라 순차적으로 정렬이 가능하다는 점과 값의 범위가 인덱스와 일치할 수 있다는 점이 문제해결의 중요한 점이었다. 때문에 정렬을 사용하지 않는 방식으로 문제를 풀어갈 수 있었다. 메모리의 차이는 체감이 없지만 해결 시간의 차이가 최대 10배 이상인 것으로 보아 활용할 수 있는 점을 찾아내는 것도 중요하다.