문제 131128. 숫자 짝꿍

문제 링크

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

프로그래머스

 

난이도 : Lv.1  

 

문제 요약 설명

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다. 예를 들어 X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요. (짝꿍이 존재하지 않는다면 -1 리턴)

 

입력

• 두 정수 X, Y가 문자열타입으로 주어집니다.

 

입력 제한

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

입력 예제

// input
"12321", "42531"  // X, Y

// ans
"321"

 

풀이 방식

X, Y 각각에 포함되어 있는 숫자의 개수를 저장하는 있는 길이 10의 배열 2개를 준비한다(배열의 index는 숫자 0~9중 하나를 의미) 배열을 거꾸로 순회하며 두 배열의 값 중 작은 값만큼 반복해서 배열의 index를 문자열(answer)에 추가한다.

배열의 순회가 끝나면(for문)  answer가 정답이 된다.

 

정답이 되는 이유

짝꿍은 X, Y에서 겹치는 숫자들의 조합 중 제일 큰 정수를 의미한다. 그렇기 때문에 준비한 배열을 거꾸로 읽으면 가장 큰 숫자인 9부터 읽게되며 자연스럽게 짝꿍의 조건을 만족한다.

정답 코드 

#include <string>
#include <vector>

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    
    vector<int> v1(10);
    vector<int> v2(10);
    
    for(char c : X){
        v1[c - '0'] ++;
    }
    
    for(char c : Y){
        v2[c - '0'] ++;
    }
    
    for(int i = 9; i >= 0; i--){
        int cnt = min(v1[i], v2[i]);
        
        if(i == 0 && answer.length() == 0){
            answer.append(min(cnt, 1), '0');
            break;
        }
        
        answer.append(cnt, '0' + i);
    }
    
    answer = answer == "" ? "-1" : answer;
    
    return answer;
}