C++ 문자열 아나그램 최소 변경 횟수

오늘 배운 핵심

문자열 비교 문제에서 순서가 아닌 “문자 개수”를 기준으로 판단하는 방법을 학습했다.
이때 freq 배열(카운팅 배열)을 사용하면 효율적으로 해결할 수 있다.

---

문제 정의

두 문자열 s1, s2가 주어졌을 때
s2를 몇 번 수정하면 s1의 아나그램으로 만들 수 있는지 구한다.

---

핵심 아이디어

길이 체크 (빠른 탈출)

if (s1.length() != s2.length()) return -1;

• 길이가 다르면 아나그램 자체가 불가능

---

Frequency Array 사용

int freq[256] = {0};

• 인덱스 = 문자 (ASCII)
• 값 = 해당 문자의 개수 차이

---

문자열 순회하며 차이 누적

freq[(unsigned char)s1[i]]++;
freq[(unsigned char)s2[i]]--;

• s1 → +1 (필요한 문자)
• s2 → -1 (현재 가진 문자)

결과:

freq[x] = s1의 개수 - s2의 개수

---

최소 변경 횟수 계산

int changes = 0;
for (int i = 0; i < 256; i++) {
    if (freq[i] > 0) {
        changes += freq[i];
    }
}

• 양수 → 부족한 문자
• 음수 → 남는 문자

부족한 문자 개수 = 바꿔야 하는 횟수

---

예시 분석

예: "abc" → "abd"

a: 0
b: 0
c: +1
d: -1

• c가 1개 부족
• d가 1개 남음

d → c로 변경 → 1번

---

예: "aabbcc" → "aabdde"

a: 0
b: +1
c: +2
d: -2
e: -1

• 부족: b 1개, c 2개 → 총 3개
• 남는 문자로 교체하면 해결

결과: 3

---

핵심 개념 정리

• 문자열 비교는 항상 순서 vs 개수를 구분해야 한다
• 이 문제는 순서 무시, 개수 비교 문제
• freq 배열은 문자 → 개수 매핑 구조

---

시간 복잡도

• O(n)
• 정렬(O(n log n))보다 효율적

---

배열 vs map

방식특징

배열(freq[256])	빠름, 코테 최적
unordered_map	유연함, 실무 적합

---

게임 개발 관점

이 개념은 다음과 같은 시스템에 활용 가능하다:

• 인벤토리 비교 (아이템 개수 차이)
• 제작 시스템 (재료 부족 계산)
• 로그 분석 (행동 빈도 비교)

---

마무리

• 처음에는 문자열을 “정렬/뒤집기”로 접근하려 했지만,
  실제로는 “문자 개수 차이”를 계산하는 문제였다.
• 문제 유형을 잘못 판단하면 시간 낭비가 크다.
• 앞으로는 “문자 개수 비교” 키워드가 보이면 freq 배열을 먼저 떠올려야 한다.

조원분께 코드를 받아 역으로 뜯어보면서 공부했다