[코딩테스트] 숫자 짝꿍

매일매일 코딩테스트 오늘의 잔디채우기는

프로그래머스 Lv.1 - 숫자 짝꿍

문제 설명

두 문자열 X, Y는 각각 숫자로만 이루어진 문자열이다.
두 문자열에서 공통으로 포함된 숫자만 추출하여 가장 큰 숫자를 만들고자 한다.

조건 요약:

• 각 문자열에 존재하는 숫자는 중복 가능하며,
  두 수에서 공통으로 등장한 숫자의 개수만큼 사용 가능
• 짝꿍이 없다면 "-1"을 리턴
• 만들어지는 수가 0만으로 이루어져 있다면 "0"을 리턴

---

핵심 포인트

• 각 숫자(0~9)의 등장 횟수를 X, Y에서 각각 세어두고
• 최소 등장 횟수만큼 결과에 포함시키는 것이 핵심
• 마지막에는 결과 숫자들을 내림차순 정렬해서 문자열로 리턴
• 예외 처리: 짝꿍 없음 → -1, 모든 숫자가 0 → "0"

 

---

 

조건 정리

조건처리	방법
X와 Y에 공통으로 나타나는 수가 없을 경우	"-1" 리턴
짝꿍 수가 전부 "0" 으로만 구성될 경우	"0" 리턴
그 외 경우	해당 숫자들을 조합하여 가장 큰 수 리턴 (내림차순 정렬 후 문자열로 반환)

---

입출력 예시

---

풀이 C++

내 풀이

문제 : 시간 초과

• std::find는 벡터를 처음부터 끝까지 순회
• str.erase(it) 도 중간 삭제

해결 : 숫자 9부터 0까지 겹치는 최소 개수만큼 추가하는 방식으로 해결

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

string solution(string X, string Y) 
{
    string answer = "";
    vector<int> temp;
    //vector<string> str;
    vector<char> str;
    //1. x와y의 공통 숫자 찾기
    //2. 공통 숫자 발견 시 제외
    //3. 숫자들 내림차순 정렬
    //4. 숫자 이어붙이기

    for(int i = 0; i < X.length(); i++)
    {
        str.push_back(X[i]);
    }
    
    for(int j = 0; j < Y.length(); j++)
    {
        //size_t pos = X.find(Y[j]);
        auto it = std::find(str.begin(), str.end(), Y[j]);
        //if(pos != string::npos)
        if(it != str.end())
        {
            int num = Y[j] - '0';
            temp.push_back(num);
            str.erase(it);
        }
    }
    
    sort(temp.begin(),temp.end(),greater<int>());
    
     for(int i = 0; i < temp.size(); i++)
     {
         answer += to_string(temp[i]);
     }
         
    // 5. 공통 숫자가 없으면 "-1" 반환
    if(answer == "") return "-1";
    
    // 6. 모든 숫자가 0이면 "0" 하나만 반환
    if(answer[0] == '0') return "0";
    
    return answer;
}

---

최적의 풀이

string(int n, char c);

• char 문자를 n개 붙인 문자열 생성

i + '0' 는 숫자를 문자로 변환하는 공식

• '0'의 아스키 값은 48
• 그래서 정수 i에 '0'을 더하면 해당 숫자 문자로 바뀜

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

string solution(string X, string Y) {
    vector<int> xCount(10, 0);
    vector<int> yCount(10, 0);

    // 0~9까지 각 숫자 개수 세기
    for (char ch : X) xCount[ch - '0']++;
    for (char ch : Y) yCount[ch - '0']++;

    string answer = "";

    // 9부터 0까지 공통 숫자 최소 개수만큼 추가
    for (int i = 9; i >= 0; i--) {
        int count = min(xCount[i], yCount[i]);
        answer += string(count, i + '0');
    }

    // 예외 처리
    if (answer.empty()) return "-1";   // 공통 숫자 없음
    if (answer[0] == '0') return "0";  // 전부 0일 경우

    return answer;
}