Map<String, Integer> dp 는 시간초과가 나는 이유 : 프로그래머스 - 사칙연산

[프로그래머스] 사칙연산 (분할정복 + DP) 풀이

[프로그래머스] 사칙연산 (분할 정복 + DP)

 

이전 풀었던 DP 문제에서 아래처럼 Map<String, Integer> 코드를 작성하면 시간 초과가 난다.

import java.util.*;

class Solution {
    static Map<String, Integer> maxMemo, minMemo;
    static String [] gArr;
    public int solution(String arr[]) {
        maxMemo = new HashMap<>();
        minMemo = new HashMap<>();
        gArr = arr;
        return getMax(0, arr.length-1);
    }
    
    private int getMax(int start, int end) {
        // 분할 범위 Key 조회
        String key = start+"+"+end;
        if (maxMemo.containsKey(key)) return maxMemo.get(key);
        // start == end 일 경우 해당 인덱스 숫자
        if (start == end) {
            int val = Integer.parseInt(gArr[start]);
            maxMemo.put(key, val);
            return val;
        }
        // start ~ end idx 범위에서 최대 연산 결과 계산
        int max = Integer.MIN_VALUE;
        for (int op = start + 1; op < end; op += 2) {
            int result;
            if (gArr[op].equals("+")) {
                // leftMax + rightMax => max
                int leftMax = getMax(start, op - 1);
                int rightMax = getMax(op + 1, end);
                result = leftMax + rightMax;
            } else {
                // leftMax - rightMin => max
                int leftMax = getMax(start, op - 1);
                int rightMin = getMin(op + 1, end);
                result = leftMax - rightMin;
            }
            max = Math.max(max, result);
        }
        maxMemo.put(key, max);
        return max;
    }
    
    private int getMin(int start, int end) {
        // 분할 범위 Key 조회
        String key = start+"+"+end;
        if (minMemo.containsKey(key)) return minMemo.get(key);
        // start == end 일 경우 해당 인덱스 숫자
        if (start == end) {
            int val = Integer.parseInt(gArr[start]);
            minMemo.put(key, val);
            return val;
        }
        // start ~ end idx 범위에서 최소 연산 결과 계산
        int min = Integer.MAX_VALUE;
        for (int op = start + 1; op < end; op += 2) {
            int result;
            if (gArr[op].equals("+")) {
                // leftMin + rightMin => min
                int leftMin = getMin(start, op - 1);
                int rightMin = getMin(op + 1, end);
                result = leftMin + rightMin;
            } else {
                // leftMin - rightMax => min
                int leftMin = getMin(start, op - 1);
                int rightMax = getMax(op + 1, end);
                result = leftMin - rightMax;
            }
            min = Math.min(min, result);
        }
        minMemo.put(key, min);
        return min;
    }
}

 

Map 탐색시 O(1) 성능을 내기에 문제는 Map 자체가 아니라, String Key 때문이다.

String key를 매우 많이 생성하고, 그 key로 빈번하게 put/get을 하기 때문에 시간초과가 발생한거다.
즉, 이론상 HashMap.get(key) 는 O(1)이라도, 실제로는 key 생성 비용과 해시 충돌로 인해 느려질 수 있다.

❗ 원인: Map<String, Integer> 의 Key 표현 방식

String key = start + "+" + end;

---

✅ 왜 String key가 느렸는가?

📌 1. key 문자열 생성 비용 (start + "+" + end)

• String key = start + "+" + end; 는 내부적으로 다음 과정을 거친다:

// InvokeDynamic #0:makeConcatWithConstants:(II)Ljava/lang/String;
→ 이건 다음과 같은 "템플릿"을 의미:
template = "\u0001+\u0001"   // 자리 2개에 정수 두 개 삽입
→ 실제 실행 시 JVM이 StringConcatFactory를 호출해서 최적화된 방식으로 "start+end" 문자열을 생성

• 즉, 문자열 덧셈으로 start + "+" + end는 매 호출마다 새로운 String 객체를 생성.
• 이걸 재귀마다 호출하면 매번 수십만 개의 문자열 객체가 생성되고 GC(가비지 컬렉션)도 작동한다.

✅ Java 8 이하
An implementation may choose to perform conversion and concatenation in one step to avoid creating and then discarding an intermediate String object. To increase the performance of repeated string concatenation, a Java compiler may use the StringBuffer class or a similar technique to reduce the number of intermediate String objects that are created by evaluation of an expression.
15.18.1. String Concatenation Operator +

✅ Java 9 이상
컴파일러는 invokedynamic + makeConcatWithConstants 방식으로 처리: (javap -c)
JEP 280: indified String Concatenation

 

📌 2. Map의 해시 충돌 & 해시 계산 비용

• HashMap.get(key)는 평균 O(1) 이지만, 내부적으로는 key.hashCode() → bucket → equals() 를 호출한다.
• String의 hashCode() 계산은 문자의 ASCII 합으로 구성된 다음과 같은 방식이다:

Returns a hash code for this string. The hash code for a String object is computed as

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]​

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)
return: a hash code value for this object.

• 이걸 key = "1+3" 같이 계속 새로 만드는 상황에선 해시 계산량이 꽤 크다
• 게다가 HashMap이 자동으로 리사이즈하거나 충돌이 발생할 경우 체이닝도 들어간다.

📌 3. 이 문제에서는 호출 횟수가 최악의 경우 수십만~백만 회

• 가능한 (start, end) 쌍은 약 O(N²)개,
• 각 쌍에서 가능한 k 분할은 또 O(N)회 → 총 약 O(N³) 연산

예를 들어 N=200인 경우 O(N³) ≈ 8,000,000
→ 그만큼 String 생성과 Map.get()/put()이 발생

---

✅ 왜 2차원 배열은 빠른가?

• dpMax[i][j] 는 정수 인덱스로 바로 접근 → 해시 계산, 객체 생성 없음
• Integer[][] 는 null 체크만 하면 끝 → 빠르고 깔끔