[프로그래머스/Day 17] 숫자 짝꿍 - Sort 대신 Map을 선택한 이유와 시간 복잡도 분석

오늘은 프로그래머스 '숫자 짝꿍' 문제를 풀기 위한 알고리즘 선택 과정과 시간 복잡도 분석을 정리해 보았습니다. 

1. 문제 개요

프로그래머스의 '숫자 짝꿍' 문제는 두 문자열 X, Y에 공통으로 존재하는 정수들을 찾아, 그 정수들을 조합해 만들 수 있는 가장 큰 수를 구하는 문제입니다.

단순히 공통된 숫자를 찾는 것을 넘어, 짝지어질 수 있는 개수만큼 숫자를 확보해야 하며 최종 결과는 내림차순으로 배치되어야 가장 큰 수가 된다는 특징이 있습니다. 만약 짝꿍이 없다면 "-1"을, 0으로만 구성되어 있다면 "0"을 반환해야 하는 예외 처리도 필요합니다.

---

2. 알고리즘 선택 과정

이 문제를 처음 접했을 때, 가장 먼저 든 생각은 인덱스를 기반으로 순회하며 해결하는 방식이었습니다.

하지만 문자열 내의 숫자가 뒤죽박죽 섞여 있기 때문에 정렬이 필수적이었습니다.

 

1) Sort 함수의 사용?
std::sort를 사용하여 두 문자열을 내림차순으로 정렬한 뒤 비교하는 방법을 고려했습니다. 하지만 sort의 시간 복잡도는 $O(N \log N)$입니다. 문제의 제한 사항 내에서는 충분히 통과할 수 있지만, N이 커질수록 효율성이 떨어지기 때문에 더 나은 방법이 있을 것이라 판단하여 일단 보류했습니다.

 

2) Set 컨테이너의 사용?
다음으로 std::set을 고려했습니다. set은 자동으로 정렬을 해주지만, 중복을 허용하지 않는다는 치명적인 단점이 있었습니다. 이 문제는 X에 '1'이 두 개, Y에 '1'이 세 개 있다면 '1'을 두 번 써야 하는 1:1 매칭 문제이므로 set은 적합하지 않았습니다.

 

3) Map 컨테이너의 선택
결국 (Key: 숫자, Value: 개수) 형태로 카운팅을 할 수 있는 std::map이 가장 적합하다고 판단했습니다. 특히 결과값이 가장 큰 수가 되어야 하므로, Map이 키를 기준으로 자동 정렬해 주는 기능을 활용하기로 했습니다.

// 내림차순 정렬을 위해 greater를 사용
map<char, int, greater<char>> xMap;
map<char, int, greater<char>> yMap;

이렇게 하면 데이터를 넣을 때부터 키값(숫자)이 큰 순서대로('9' -> '0') 정렬되므로 나중에 별도로 정렬할 필요가 없어집니다.

 

🚧 마주친 난관
하지만 구현 단계에서 고민이 생겼습니다.

"두 Map의 원소 개수도 다르고, 들어있는 키의 종류도 다른데 어떻게 비교를 해야 할까?"

두 Map을 동시에 iterator로 돌리기에는 조건 분기가 복잡해질 것 같았고, 효율적인 비교 방법에 대한 확신이 서지 않았습니다.

---

3. 비교 로직 정립 및 시간 복잡도 분석

1) Map 간의 비교 해결
두 Map을 동시에 순회할 필요가 없다는 점을 깨달았습니다. 이미 xMap은 greater 조건에 의해 '9'부터 '0'까지 내림차순으로 정렬되어 있습니다. 따라서 xMap을 기준으로 순회하면서, 현재 키가 yMap에도 존재하는지 확인만 하면 됩니다.

• xMap의 키(숫자)가 yMap에도 있다면? -> 두 Map의 Value(개수) 중 최솟값만큼 결과 문자열에 추가합니다.
• xMap의 키가 yMap에 없다면? -> 그냥 넘어갑니다.

이 방식을 사용하면 복잡한 인덱스 관리 없이 깔끔하게 공통된 숫자를 큰 수부터 추출할 수 있습니다.

 

2) 시간 복잡도 의문 해결: Sort vs Map
처음에 sort ()를 피하기 위해 Map을 선택했는데, "과연 Map에 데이터를 넣는 과정은 얼마나 빠를까?"라는 의문이 들었습니다.

• Map의 삽입 복잡도: map은 내부적으로 균형 이진 트리(Red-Black Tree)로 구현되어 있습니다. 원소 하나를 삽입/검색하는 데 $O(\log K)$의 시간이 걸립니다. (는 Map의 크기)
• 이 문제에서의 특수성: 여기서 Key는 '0'~'9'인 숫자 문자입니다. 즉, Map에 들어가는 고유한 키의 개수()는 아무리 많아봤자 최대 10개입니다.
• 결론: 문자열의 길이가 일 때, 전체 삽입 과정은 $O(N \log 10)$입니다. 은 상수이므로, 실질적인 시간 복잡도는 $O(N)$에 가깝습니다.

따라서 $O(N \log N)$인 정렬 방식보다 이론적으로 더 효율적인 접근임을 확신할 수 있었습니다.

---

4. 최종 코드

위의 사고 과정을 통해 완성된 코드는 다음과 같습니다. map의 템플릿 인자로 greater<char>를 사용하여 내림차순 정렬을 자동화했고, min 함수를 통해 공통된 개수를 산출했습니다.

#include <algorithm>
#include <map>
#include <string>

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    
    // Key: 숫자문자, Value: 개수, 정렬: Key 기준 내림차순 ('9' -> '0')
    map<char, int, greater<int>> xMap;
    map<char, int, greater<int>> yMap;
    
    // 1. map 내림차순으로 각 문자열 X, Y를 분해한다.
    for(char c : X) xMap[c]++;
    for(char c : Y) yMap[c]++;
    
    // 2. xMap을 기준으로 순회한다.
    for(auto iter = xMap.begin(); iter != xMap.end(); iter++) {
        char key = iter->first;    // 현재 숫자
        int xCount = iter->second; // X에 있는 개수
        
        // 3. 같은 원소가 yMap에 존재하는지 확인
        if(yMap.count(key)) {
            int yCount = yMap[key]; // Y에 있는 개수
            
            // 두 개수 중 최솟값만큼 answer에 이어 붙인다.
            int commonCount = min(xCount, yCount);
            for(int i = 0; i < commonCount; i++) {
                answer += key;
            }
        }
    }
    
    // 4. answer의 길이가 0이면 "-1"을 반환한다.
    if(answer == "") return "-1";
    
    // 5. "00" 같은 형태로 존재하는 경우 "0" 하나만 반환한다.
    if(answer[0] == '0') return "0";
     
    return answer;
}