단순 구현에서 시간 복잡도 최적화까지 – 삽질 기록(카운팅배열)

KUN·2025년 6월 15일

계기

위 문제를 풀기 위해서 다음과 같이 코드를 짰으나,
시간 복잡도에서 과감하게 털렸다.

class Solution {
    /*
        char 형식으로 1개씩 x 에서 뽑는다.
        
        x = 5, 5, 2, 5
        그리고 y 에서 5를 찾아서 맨 앞에를 삭제한다. 그리고 x 에서도 삭제한다.
        배열 arr 에다가 삭제된 5를 저장한다.
        
        배열 arr 이 완성되면 이들의 숫자중 가장 큰 수를 만든다.
        가장 큰 수를 맨앞에 두도록 정렬하면 끝
    */
    public String solution(String x, String y) {
        StringBuilder builder = new StringBuilder();
        for( char v : x.toCharArray() ){
            String c = String.valueOf(v);
            if ( y.contains(c) ){
                builder.append(c);
                y = y.replaceFirst(c,"");
            }
        }
        
        char[] arr = builder.toString().toCharArray();
        if ( arr.length == 0 ) return "-1";
        for ( int i = 0; i<arr.length-1;i++){
            for ( int j = i+1; j<arr.length; j++){
                if ( arr[i] < arr[j]){
                    char temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        
        builder = new StringBuilder();
        String v2 = builder.append(arr).toString();
        while (v2.startsWith("0")){
            v2 = v2.replaceFirst("0","");
        }
        return v2.isEmpty() ? "0" : v2;
    }
}

문제점 인식

무엇 때문에 시간 복잡도에서 오래걸렸나 고민을 해보면 다음과 같은 결론이 나왔다.

1번째 문제

for( char v : x.toCharArray() ) 를 하여 x 만큼 반복
y.contains(c) 을 진행하면서 내부적으로 반복이 또 들어간다.
y.replaceFirst() 는 y 문자열을 다시 탐색해서 해당 문자를 찾아 새 문자열로 복사한다.
그렇게 된다면 시간 복잡도는 O(n x m) 이 된다.

2번째 문제

흔한 선택정렬이다.
각 자리를 기준으로, 그 뒤에 있는 값들과 하나씩 비교하면서 더 큰 값을 찾아 swap하는 구조다.
시간 복잡도는 O(n²)로, 데이터가 많아질수록 성능에 큰 영향을 준다.

3번째 문제

정렬된 결과에서 앞쪽의 0을 제거하려고 startsWith와 replaceFirst를 반복 사용했는데,
최악의 경우를 생각해보면 0000000000123 값이 들어올 경우 9 × O(n) = O(n²) 상황이 온다.

정리하면?

공통 숫자 추출: O(n × m)
선택 정렬: O(n²)
앞자리 0 제거: O(n²)

문자열 길이가 약 3,000자 정도일 경우,
최악의 경우 총 2천만 번 이상의 연산이 발생하게 된다.

해결방안

1. 퀵 정렬(실패)

처음에 선택 정렬로 인해서 정렬이 매우 느리다 생각했다.
그래서 검색해서 가장 빠른 정렬을 할 수 있는 퀵 정렬 이라는 걸 알아냈다.

알고리즘을 직접 구현하는 방법도 있지만,
Arrays.sort() 라는 좋은 기능이 있다.

결국 이것도 퀵정렬, 일반적인 퀵정렬보다 더 최적화된 방식이다.

결과는 똑같이 시간초과가 된다.

2. 카운팅 정렬(성공)

퀵정렬을 사용해 시간 복잡도를 개선해보았지만,
여전히 공통 숫자를 찾는 과정에서 시간 초과가 발생했다.

이때 문득, 문제의 특성이 떠올랐다.

입력은 모두 0~9까지의 숫자 문자열

즉, 값의 범위가 매우 작고 고정되어 있다.

이런 경우, 굳이 비교 기반 정렬을 쓰지 않아도
숫자의 개수만 세는 방식으로 충분히 해결 가능하지 않을까? 하는 생각이 들었다.

가정

만약 5525 와 11552 가 나온다면, 5,5,2 가 나와야한다.
A 배열은 2: 1개, 5: 3개
B 배열은 1: 2개, 2: 1개, 5: 2개
복잡한 문자열 반복 없이,
각 숫자의 등장 횟수만 비교하면 정답을 쉽게 만들 수 있다.

이런방법이 뭐가 있나 했더니 카운팅 정렬 이라는 방식이 있다.
카운팅 정렬(Counting Sort, 계수 정렬) 알고리즘 해당 블로그를 참조해서 만들어보겠다.

해결과정

0 ~ 9 까지 총 10개의 숫자가 들어가기 때문에 10개의 자릿수가 들어가는 배열 2개를 만든다.
c는 문자 '0'부터 '9' 사이의 문자이다.
'0'은 아스키 코드로 48 -> c - '0' 하면 실제 정수 0~9로 변환되며,
countX[5]++ > x 문자열에 '5'가 한 번 나왔다고 기록한다.