[내배캠 TIL 260430] C++ 숫자 짝꿍 (빈도수 배열 최적화)

1. 문제 핵심

• 두 문자열 X, Y에서 공통 숫자로 만들 수 있는 가장 큰 수
• 길이 최대 3,000,000 → 시간복잡도 중요

---

2. 기존 방식 문제

• sort + 이중 반복문

정렬: O(N log N)
탐색: O(N^2) (최악)

 

• 중복 비교 많아서 시간 초과 위험

---

3. 해결 방법

핵심 아이디어

• 숫자는 0~9 → 종류가 고정됨
• 배열로 카운팅

---

시간복잡도

O(N)

 

• 정렬 없음
• 이중 반복 없음

---

4. 코드

 

string solution(string X, string Y) {
    string answer = "";
    int countX[10] = {0};
    int countY[10] = {0};

    for (char c : X) countX[c - '0']++;
    for (char c : Y) countY[c - '0']++;

    for (int i = 9; i >= 0; i--) {
        int common = min(countX[i], countY[i]);
        for (int j = 0; j < common; j++) {
            answer += to_string(i);
        }
    }

    if (answer == "") return "-1";
    if (answer[0] == '0') return "0";

    return answer;
}

 

---

5. 핵심 포인트

• 값의 범위가 작으면 → 배열 카운팅이 최적
• 정렬 대신 순회 순서로 정렬 효과 만들기
• 문자열 문제라도 연산 전에 복잡도 먼저 계산

---

6. 오늘의 교훈

• 정렬부터 쓰는 습관 버리기
• 범위 제한 보이면 카운팅 먼저 떠올리기
• 성능은 결국 자료구조 선택에서 갈린다