[알고리즘] 숫자 짝꿍

문제 분석: 숫자 짝꿍

핵심 요구사항

• 두 문자열 X, Y에서 공통으로 나타나는 숫자를 찾되, 짝지을 수 있는 개수만큼만 사용
• 그 숫자들로 만들 수 있는 가장 큰 정수를 문자열로 반환
• 공통 숫자가 없으면 "-1", 공통 숫자가 모두 0이면 "0" 반환
• X, Y의 길이가 최대 3,000,000으로 매우 큼 → 효율적인 알고리즘 필수

Problem

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.
제한사항
3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.X, Y는 0으로 시작하지 않습니다.X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

My Solution 

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        TreeMap<Character, Integer> mapX = stringToMap(X);
        TreeMap<Character, Integer> mapY = stringToMap(Y);
        TreeMap<Character, Integer> mapXY = findCommonMap(mapX, mapY);
        answer = toPair(mapXY);
        return answer;
    }
    
    // 1. 문자열을 TreeMap으로 바꿔주는 함수
    private TreeMap<Character, Integer> stringToMap(String s) {
        TreeMap<Character, Integer> map = new TreeMap<>();
        for (char c : s.toCharArray()) {
            map.merge(c, 1, Integer::sum);   
        }
             return map;
    }
    // 2. 두 TreeMap을 받아 공통된 key-value로 구성된 TreeMap을 반환하는 함수
    private TreeMap<Character, Integer> findCommonMap(TreeMap<Character, Integer> mapX, TreeMap<Character, Integer> mapY) {
        TreeMap<Character, Integer> commonTreeMap = new TreeMap<>(Comparator.reverseOrder());
        for(Map.Entry<Character, Integer> entry : mapX.entrySet()) {
            Character key = entry.getKey();
            if (mapY.containsKey(key)) {
                commonTreeMap.put(key, Math.min(entry.getValue(), mapY.get(key)));
            }
        }
        return commonTreeMap;
    }
    // 3. TreeMap을 받아 짝꿍을 계산하여 return하는 함수
    private String toPair(TreeMap<Character, Integer> map) {
        if(map.isEmpty()) return "-1";
        if(map.firstKey().equals('0')) return "0";
        
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer>  entry : map.entrySet()) {
            sb.append(String.valueOf(entry.getKey()).repeat(entry.getValue()));
        }
        return sb.toString();
    }
}
/*
#1
100
2345

map으로 저장(숫자, 횟수)
map은 불변과 가변 맵이 있음 -> 가변 맵인 HashMap<>을 사용해야 숫자를 읽으면서 추가 가능
TreeMap은 키 기준 오름차순 정렬해줌 -> 내림차순은 Comparator.reverseOrder()를 인수로 넣어주면 됨
mapX = new TreeMap<String, Integer>(Comparator.reverseOrder())
mapY = new TreeMap<String, Integer>(Comparator.reverseOrder())
mapX = {"1",1,"0",2}
mapY = {"5", 1, "4",1, "3",1,"2", 1}
겹치는 키가 없으므로 -1


#2
100
203045
mapX = {"1", 1, "0", 2}
mapY = {"5",1, "4", 1, "3", 1, "2", 1, "0", 2}
0 두개 겹침 -> "00" -> 0으로 시작하면 0으로 반환

#3
12321
42531

mapX = {"3", 1, "2", 2, "1", 2}
mapY = {"5", 1, "4", 1, "3", 1, "2", 1, "1", 1}
mapXY = {"3", 1, "2", 1, "1", 1}
return 321

1. 문자열을 TreeMap으로 바꿔주는 함수
2. 두 TreeMap을 받아 공통된 key-value로 구성된 TreeMap을 반환하는 함수
3. TreeMap을 받아 짝꿍을 계산하여 return하는 함수

*/

 

Strengths:

접근 방식 분석

stringToMap → findCommonMap → toPair 의 3단계로 책임을 분리한 구조입니다.

1. 각 문자열을 TreeMap<Character, Integer>로 변환해 자릿수 빈도를 저장
2. 두 맵의 공통 키에 대해 min(countX, countY)로 짝 지을 수 있는 개수를 계산, 내림차순 TreeMap에 저장
3. 내림차순으로 정렬된 맵을 순회하며 결과 문자열 생성

핵심 아이디어가 정확합니다. 숫자는 0~9 범위이므로 빈도 카운트 방식이 최적입니다.

구분	복잡도	설명
시간	O(N + M)	X 길이 N, Y 길이 M 순회. TreeMap의 키 범위가 0~9로 고정(최대 10개)이므로 삽입/탐색이 사실상 O(1)
공간	O(N + M)	toCharArray()가 각각 길이만큼 배열을 생성

 

• 책임 분리가 명확합니다. 각 함수가 하나의 역할만 하므로 가독성과 유지보수성이 높습니다.
• map.merge() 를 사용해 빈도 카운트 코드가 간결합니다.
• StringBuilder 를 사용해 문자열 반복 연결 시 불필요한 객체 생성을 방지했습니다.
• 엣지 케이스 처리(-1, 0)가 toPair에 명확히 분리되어 있습니다.

 

Limitations (or Trade-offs):

1. toCharArray()의 메모리 비효율 (가장 중요)
X, Y가 최대 300만 자리이므로 s.toCharArray()는 매번 길이만큼 새 char[] 배열을 힙에 할당합니다. charAt(i)로 인덱스 접근하면 배열 복사 없이 순회할 수 있습니다.
2. TreeMap 대신 int[10] 배열이 더 적합
키가 '0'~'9'로 딱 10개로 고정되어 있어 TreeMap의 자동 정렬 기능이 실질적인 이점이 없습니다. int[10] 배열을 쓰면 해시/비교 오버헤드가 없고, 내림차순 순회도 단순 역방향 루프로 처리할 수 있어 속도와 메모리 모두 유리합니다.
3. toPair의 TreeMap.firstKey()로 '0' 체크하는 로직
현재 commonTreeMap이 내림차순으로 정렬되어 있어 firstKey()가 가장 큰 키를 반환합니다. firstKey() == '0'이라면 공통 숫자가 '0'뿐이라는 의미인데, 이 조건이 직관적으로 바로 이해되지 않습니다. int[10] 배열로 바꾸면 이 케이스도 자연스럽게 처리됩니다.
4. String.valueOf(entry.getKey()).repeat()
Character를 String으로 변환 후 repeat()하는 것보다, char를 직접 sb.append()하는 것이 더 간단합니다.

---

Example (Key Idea: )

class Solution {
    public String solution(String X, String Y) {
        // 0으로 초기화
        int[] countX = new int[10]; 
        int[] countY = new int[10];
        
        // 각 문자열의 자릿수를 순회하며 숫자별 빈도를 카운팅하여 배열에 업데이트
        // 각 배열의 인덱스는 0부터 9까지의 자릿수를 의미하며, 배열의 값은 빈도 수를 의미
        count(X, countX);
        count(Y, countY);
        
        // 배열을 뒤에서부터 순회하며 더 작은 값을 선택하여 새로운 문자열 생성
        // StringBuilder 사용하여 메모리 공간 절약
        StringBuilder sb = new StringBuilder();
        for(int i = 9; i >= 0; i--) {
            int min = Math.min(countX[i], countY[i]);
            for(int j = 0; j < min; j++) {
                sb.append(i);
            }
        }
        
        if(sb.length() == 0) return "-1";
        if(sb.charAt(0) == '0') return "0";
        return sb.toString();
    }
    
    private void count(String s, int[] arr) {
        for(int i = 0; i < s.length(); i++) {
            arr[Character.getNumericValue(s.charAt(i))]++; // 아래 코드로도 대체 가능하나, 이게 best
            // arr[(int)s.charAt(i) - '0']++;
        }
    }
}
/*
어제 간과했던 부분
1. x,y의 자릿수 : 최소 3에서 최대 3백만
2. x,y는 문자열 형태의 양의 정수

새롭게 알게 된 것
1. string.charAt(i) 메서드를 사용하면 메모리를 추가로 할당할 필요가 없다. 단순 조회 용도라면 toCharArray() 대신 charAt(i)를 사용하자. 
2. s.charAt(i)는 문자의 ASCII 코드값을 반환함. '0'의 코드값은 48, '9'는 57이므로 배열 크기인 10을 넘어가므로 ArrayIndexOutOfBounds이 발생
*/

Strengths

• int[10] 빈도 배열을 사용한 접근은 이 문제에서 최선의 선택
• 시간/공간 복잡도 최적화: 빈도 배열은 O(1) 공간(크기 10 고정)을 사용하고, 전체 탐색은 O(N)으로 3백만 자리도 문제없이 처리
• charAt(i) 사용: toCharArray() 대신 charAt(i)를 사용하여 불필요한 배열 복사를 피한
• StringBuilder 활용: 문자열 연결을 + 대신 StringBuilder로 처리하여 O(N²) 문자열 복사를 방지했습니다.
• 엣지 케이스 처리: 짝꿍이 없는 경우 "-1", 0만 있는 경우 "0" 처리가 올바릅니다.

성능 개선

메모리 사용량 : 178MB > 145MB
실행 시간 : 322ms -> 91ms

 

My Github Repository for Solution Code

[level 1] Title: 숫자 짝꿍, Time: 322.05 ms, Memory: 178 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@f8bc298

 

Problem Source

프로그래머스