프로그래머스 [연습문제 / 숫자 짝꿍](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 131128 숫자 짝꿍

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/131128

문제 설명:

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수를 이용하여 만들 수 있는 가장 큰 정수를 짝꿍이라고 합니다. 공통 정수 중 서로 짝지을 수 있는 숫자만 사용하며, 짝꿍이 없으면 -1을, 0으로만 구성되면 0을 반환합니다. 문자열의 길이가 최대 300만까지 가능하므로 효율적인 알고리즘이 필요한 해시 테이블 문제입니다.

---

문제 해결 코드

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

string solution(string X, string Y) {
    string answer = "";
    
    // 0~9 각 숫자의 등장 횟수를 저장할 배열
    int countX[10] = {0};
    int countY[10] = {0};
    
    // X의 각 숫자 등장 횟수 카운트
    for(char x : X) {
        countX[x - '0']++;
    }
    
    // Y의 각 숫자 등장 횟수 카운트
    for(char y : Y) {
        countY[y - '0']++;
    }
    
    // 9부터 0까지 역순으로 순회하여 가장 큰 수 만들기
    for(int i = 9; i >= 0; i--) {
        // 두 숫자 중 최소 등장 횟수만큼만 사용 가능
        int minCount = (countX[i] < countY[i]) ? countX[i] : countY[i];
        
        // 해당 숫자를 minCount번 반복하여 추가
        for(int j = 0; j < minCount; j++) {
            answer += to_string(i);
        }
    }
    
    // 공통 숫자가 없는 경우
    if(answer == "") {
        answer = "-1";
    }
    // 0으로만 구성된 경우 (예: "000" → "0")
    else if(answer[0] == '0') {
        answer = "0";
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 해시 테이블(배열) 방식을 사용합니다. X와 Y를 직접 비교하는 대신, 0~9 각 숫자의 등장 횟수를 배열로 저장합니다. 두 배열에서 같은 인덱스의 최소값이 공통으로 사용 가능한 숫자의 개수가 됩니다. 가장 큰 수를 만들기 위해 9부터 0까지 역순으로 순회하며 결과 문자열을 구성합니다.
• 구현 세부사항:
  • 크기 10인 배열 두 개로 0~9 각 숫자의 등장 횟수를 O(n) 시간에 계산합니다.
  • 각 문자에서 '0'을 빼면 숫자로 변환되어 배열 인덱스로 사용할 수 있습니다.
  • 9부터 0까지 역순으로 순회하여 큰 숫자부터 배치하므로 별도 정렬이 불필요합니다.
  • 두 배열의 최소값만큼만 해당 숫자를 결과에 추가합니다.
  • 빈 문자열은 공통 숫자가 없는 경우이므로 -1을 반환합니다.
  • 첫 문자가 0이면 모든 공통 숫자가 0이므로 "0"을 반환합니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n + m)입니다. 여기서 n과 m은 X와 Y의 길이입니다. 각 문자열을 한 번씩 순회하여 등장 횟수를 세고, 0~9까지 상수 시간에 결과를 구성합니다. 공간 복잡도는 O(1)입니다. 크기가 10으로 고정된 배열 두 개만 사용하므로 입력 크기와 무관하게 일정한 메모리를 사용합니다.

---

실행 예시

테스트 케이스 1:

입력: X = "100", Y = "2345"

실행 과정:

• countX = [2, 1, 0, 0, 0, 0, 0, 0, 0, 0] (0이 2개, 1이 1개)
• countY = [0, 0, 1, 1, 1, 1, 0, 0, 0, 0] (2, 3, 4, 5가 각 1개)
• 공통 숫자 없음 (모든 인덱스에서 최소값이 0)

출력: "-1"

테스트 케이스 2:

입력: X = "100", Y = "203045"

실행 과정:

• countX = [2, 1, 0, 0, 0, 0, 0, 0, 0, 0]
• countY = [2, 0, 1, 1, 1, 1, 0, 0, 0, 0]
• 공통: 0이 2개 → "00"
• 모두 0이므로 "0" 반환

출력: "0"

테스트 케이스 3:

입력: X = "12321", Y = "42531"

실행 과정:

• countX = [0, 2, 2, 1, 0, 0, 0, 0, 0, 0]
• countY = [0, 1, 1, 1, 1, 1, 0, 0, 0, 0]
• 공통: 3이 1개, 2가 1개, 1이 1개
• 9부터 역순: "321"

출력: "321"

---

결과

해시 테이블 방식으로 문자열 길이가 최대 300만인 경우에도 효율적으로 처리할 수 있습니다. 직접 비교 방식은 O(n ⋅ m)의 시간 복잡도로 시간 초과가 발생하지만, 등장 횟수를 세는 방식은 O(n + m)으로 획기적으로 개선됩니다. 9부터 역순으로 순회하여 결과를 구성하므로 별도 정렬이 불필요하며, 메모리도 상수 공간만 사용하는 최적의 솔루션입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!