<프로그래머스 C++> 두 수의 짝꿍 풀이

문제

두 수의 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수들을 이용해서 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라고 한다.

단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용한다.

X, Y의 짝꿍이 존재하지 않으면 -1을 반환, 짝꿍이 0으로만 구성되어 있으면 0을 반환

---

문제 흐름 파악

두 수에서 공통으로 짝지을 수 있는 숫자를 찾아서 가장 큰 수를 만들면 된다.

 

예시에 있던 숫자들을 보자.

 

X = 3403 

0 << 1개, 3 << 2개, 4 << 1개

 

Y = 132030

0 << 2개, 1 << 1개, 2 << 1개, 3 << 2개

 

공통 개수

min(x개수, y개수)

0 << min(1,2) = 1개

3 << min(2, 2) = 2개

 

공통 숫자는 그럼 3, 3, 0 이므로 330을 출력하면 된다.

---

문제 풀이

#include <string>
#include <vector>

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    int cntX[10] = {0};
    int cntY[10] = {0};
    
    for(char c : X) cntX[c - '0']++;
    for(char c : Y) cntY[c - '0']++;

    for(int i=9; i>=0; --i)
    {
        int common = min(cntX[i], cntY[i]);
        for(int k=0; k<common; ++k)
        {
            answer += (char)('0' + i);
        }
    }
    
    if(answer.empty()) return "-1";
    if(answer[0] == '0') return "0";
    
    return answer;
}

 

코드 흐름

1. 각 숫자 (0 ~ 9)의 빈도 세기

for(char c : X) cntX[c - '0']++;
for(char c : Y) cntY[c - '0']++;

 

cntX [ c - '0' ] 부분에서 c 에서 '0'을 빼면 해당 정수값이 나온다. 따라서 해당 숫자의 카운트를 세서 저장할 수 있다.

 

2. 공통 개수만큼 내림차순으로 추가

for(int i=9; i>=0; --i)
{
    int common = min(cntX[i], cntY[i]);
    for(int k=0; k<common; ++k)
        answer += (char)('0' + i);
}

9 ~ 0 순서대로 탐색해서 자동으로 내림차순 정렬이 되도록 했다.

공통 개수만큼 해당 숫자를 문자로 변환해서 answer에 이어붙인다.

 

3. 예외 케이스 처리

if(answer.empty()) return "-1";   // 공통 숫자가 없음
if(answer[0] == '0') return "0";  // 공통 숫자가 0뿐

큰 숫자부터 내림차순으로 처리했기 때문에 맨 처음 숫자가 0이면 0으로 이루어진 숫자 정렬이라는 뜻이다.

그래서 첫 숫자가 0이라면 0을 리턴해도 괜찮다.

---

핵심 포인트

1. 문자열을 숫자로 변환하지 않고 자릿수만 셈

X, Y의 길이가 최대 300만이므로 정수로 변환하면 범위를 초과한다. 문자열을 순회하며 각 자리의 숫자의 빈도만 세면 O(n)으로 해결된다.

 

2. c - '0'으로 문자 > 정수로 변환

char 타입은 내부적으로 ASCII코드로 저장되기 때문에, 문자에서 '0'을 빼면 정수값을 얻을 수 있다.

 

3. 9 ~ 0 순서로 탐색해서 자동으로 내림차순 정렬

큰 숫자부터 자동으로 내림차순 되도록 answer에 추가함