[C++] 프로그래머스 숫자 짝꿍

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

프로그래머스

풀이

두 문자열 X, Y가 주어졌을 때, 공통 문자를 찾은 후 가장 큰 문자열로 변환하여 리턴하는 문제입니다.

 

공통 문자열을 찾기위해 map자료구조를 통해 해싱하는 방법을 사용했습니다. 

X, Y 문자열에서 문자 갯수 카운트용 변수 x_um, y_um 을 선언하고 각 문자마다 등장한 갯수를 기록해둡니다.

다음으로, x_um에 기록된 문자가 y_um 에서도 등장했다면 더 적은 등장횟수만큼 answer에 추가해줍니다. 이때, 어차피 공통 문자를 찾는 것이므로 x_um을 순회하든, y_um을 순회하든 상관없습니다.

 

순회가 종료된 후, answer가 비어있다면 짝꿍이 존재하지 않으므로 "-1"을 리턴해줍니다. 비어있지 않다면, 리턴해야 하는 값은 가장 큰 수여야 하므로 sort 를 사용해 내림차순으로 정렬해줍니다. 이 때, 가장 앞에 '0'이 존재한다면 '0'을 리턴해야 함에 유의합니다.

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

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    unordered_map<char, int> x_um;
    unordered_map<char, int> y_um;
    // 공통 문자 찾기 & 갯수 기록
    for (auto i:X) x_um[i]++;
    for (auto i:Y) y_um[i]++;
    
    for (auto i:x_um) {
        // X에서 나타난 것이 Y에도 있다면 더 적은 숫자만큼 기록
        if (y_um[i.first]) {
            if (i.second < y_um[i.first]) {
                for (int cnt = 0; cnt < i.second; cnt++)
                    answer+= i.first;
            }
            else {
                for (int cnt = 0; cnt < y_um[i.first]; cnt++) 
                    answer+= i.first;
            }
        }
    }
    // 짝꿍이 없는 경우
    if (answer == "")
        return "-1";
    
    // 내림차순 정렬
    sort(answer.begin(), answer.end(), greater<>());
    // 처음 나타난 수가 0이면 "0" 리턴
    if (answer[0] == '0')
        return "0";
    return answer;
}