map과 배열의 코드 효율성 비교

🔍 비교

📌 내 코드

#include <string>
#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

int solution(string str1, string str2) {
    map<string, int> mp1, mp2; // 다중집합 저장
    
    // 다중집합 생성
    for (int i = 1; i < str1.length(); i++) {
        char a = toupper(str1[i - 1]);
        char b = toupper(str1[i]);
        if (isalpha(a) && isalpha(b)) {
            string tmp = {a, b};  
            mp1[tmp]++;
        }
    }
    for (int i = 1; i < str2.length(); i++) {
        char a = toupper(str2[i - 1]);
        char b = toupper(str2[i]);
        if (isalpha(a) && isalpha(b)) {
            string tmp = {a, b};
            mp2[tmp]++;
        }
    }

    // 교집합과 합집합 계산
    int inter_size = 0, uni_size = 0;
    for (const auto& [key, val] : mp1) {
        if (mp2.count(key)) {
            inter_size += min(val, mp2[key]);
            uni_size += max(val, mp2[key]);
        } else {
            uni_size += val;
        }
    }
    for (const auto& [key, val] : mp2) {
        if (!mp1.count(key)) {
            uni_size += val;
        }
    }

    // 자카드 유사도 계산
    double jaccard = (uni_size == 0) ? 1.0 : (double) inter_size / uni_size;
    return (int)(jaccard * 65536);
}

---

📌 비교할 코드 (short 배열 사용)

#include <bits/stdc++.h>
using namespace std;
short a, b, C[676], D[676];
int solution(string A, string B) {
    for(int i=1; i<A.size(); i++)
        if(isalpha(A[i-1]) && isalpha(A[i]))
            C[(A[i-1]&31)*26+(A[i]&31)]++;
    for(int i=1; i<B.size(); i++)
        if(isalpha(B[i-1]) && isalpha(B[i]))
            D[(B[i-1]&31)*26+(B[i]&31)]++;
    for(int i=0; i<676; i++) a+=min(C[i], D[i]), b+=max(C[i], D[i]);
    return b ? a*65536/b : 65536;
}

---

🔬 성능 비교

비교 항목	기존 코드 (map 사용)	새로운 코드 (배열 사용)
데이터 구조	map<string, int> 사용 (해시맵)	short[676] 배열 사용
시간 복잡도	O(N log N) (맵 삽입 및 탐색)	O(N) (배열 접근)
공간 복잡도	O(K) (K는 2-gram 조합 개수)	O(1) (short[676] 고정 크기)
대소문자 처리	toupper() 사용	&31 비트 연산 사용
메모리 사용량	동적 메모리 할당 (맵 크기에 따라 증가)	정적 메모리 할당 (고정 크기 676)

---

📊 분석 및 결론

✅ 1. 속도 (배열 사용 코드가 더 빠름)

• 기존 코드(map<string, int> 사용)
  • 해시맵(map<string, int>)을 사용하므로, 키를 탐색하는 데 O(log K) 연산이 필요함.
  • 키를 비교할 때 string을 사용하기 때문에 상대적으로 연산이 느림.
• 새로운 코드(short[676] 배열 사용)
  • 배열 인덱스 접근은 O(1) 이므로, 전체 연산이 O(N) 으로 최적화됨.
  • 비트 연산(&31)을 사용하여 대소문자 변환을 빠르게 처리함.

✅ 배열을 사용한 코드가 더 빠름 (시간 복잡도가 O(N log N)에서 O(N)으로 개선됨).

---

✅ 2. 메모리 사용량 (배열 코드가 더 적게 사용)

• 기존 코드에서는 해시맵(map<string, int>)을 사용하여 입력 크기에 따라 동적으로 메모리를 할당함.
• 새로운 코드에서는 고정 크기 배열 (short[676]) 을 사용하여 메모리를 절약함.

✅ 배열 코드가 더 적은 메모리를 사용함.

---

✅ 3. 코드 가독성

• 기존 코드에서는 map을 사용하여 다중집합을 구성하는 것이 명확하지만, 문자열 키를 사용해야 하는 점이 복잡함.
• 새로운 코드에서는 알파벳을 정수 인덱스로 변환하여 배열을 직접 접근하므로, 코드가 짧고 단순함.

✅ 배열 코드가 더 직관적이고 간결함.

---

📌 결론

✅ 배열(short[676])을 사용한 코드가 더 효율적이며 성능이 좋다.

• 시간 복잡도: O(N log N) → O(N) 으로 개선됨
• 메모리 사용량: 동적 할당(map)보다 정적 배열이 더 적게 사용됨
• 가독성: 코드가 더 단순하고 직관적임

---

---

---

++추가) 코드 해석

🔍 676 크기의 배열을 사용한 이유

676 크기의 배열을 사용한 이유는 영어 알파벳 2-gram(두 글자 조합) 개수를 표현하기 위해서

1. 2-gram의 개수 계산

• 입력 문자열에서 연속된 두 개의 문자(2-gram) 를 추출하여 비교하는 방식
• 영어 알파벳(A-Z, a-z)은 총 26자
• 대소문자를 구분하지 않으므로 대문자로 변환(A-Z) 하면 26개의 문자만 남음.
• 두 글자로 이루어진 조합(2-gram)의 개수:
  26 * 26 = 676
  즉, "AA"부터 "ZZ"까지 총 676개의 조합이 가능
• 따라서 C[676], D[676] 배열을 선언하여 각 2-gram의 개수를 저장할 수 있음

---

🔍 배열 인덱싱 방식: (A[i-1] & 31) * 26 + (A[i] & 31)

C[(A[i-1] & 31) * 26 + (A[i] & 31)]++;

이 부분에서 & 31 연산을 사용하여 알파벳을 숫자로 변환

2. & 31 연산이 의미하는 것

문자의 ASCII 값을 변환할 때 대문자와 소문자를 동일하게 처리하기 위해 사용됨

문자	ASCII 값	& 31 결과
'A'	65	1
'B'	66	2
...	...	...
'Z'	90	26
'a'	97	1
'b'	98	2
...	...	...
'z'	122	26

즉, 대소문자 상관없이 'A'~'Z'를 1~26으로 변환할 수 있음.

3. 2-gram을 인덱스로 변환하는 공식

(A[i-1] & 31) * 26 + (A[i] & 31)

• 첫 번째 문자: A[i-1] & 31 (1~26)
• 두 번째 문자: A[i] & 31 (1~26)
• 배열 인덱스:
  {(첫 번째 문자 - 1)} * 26 + ({두 번째 문자 - 1})
• 예제:
  • "AB" → (1 * 26 + 2) = 28
  • "ZZ" → (26 * 26 + 26) = 675

이렇게 하면 각 2-gram을 0~675 범위의 배열 인덱스로 저장할 수 있음.

---

🔍 교집합 & 합집합 구하기

for(int i=0; i<676; i++) 
    a += min(C[i], D[i]), 
    b += max(C[i], D[i]);

• a → 교집합 크기 (두 배열에서 같은 2-gram의 최소 등장 횟수)
• b → 합집합 크기 (두 배열에서 같은 2-gram의 최대 등장 횟수)

4. min()과 max()를 사용한 이유

(1) 교집합

• min(C[i], D[i])
  • 예를 들어, C[i] = 2, D[i] = 3이면 교집합은 2개
  • 즉, 두 개의 집합에서 공통으로 포함된 개수를 합산.

(2) 합집합

• max(C[i], D[i])
  • 예를 들어, C[i] = 2, D[i] = 3이면 합집합은 3개
  • 즉, 두 개의 집합에서 최소한 한 번이라도 포함된 개수를 합산.

5. Jaccard 유사도 계산

return b ? a * 65536 / b : 65536;

• Jaccard Similarity = (교집합 크기) / (합집합 크기)
• 자카드 유사도를 65536 범위로 정규화하여 반환.
• 합집합이 0일 경우(둘 다 공집합이면) 100% 유사도로 처리 (65536 반환).

---

---

비트 연산과 정적 배열을 잘 활용하는 방법을 배운 풀이과정이었다..