2026-04-02 TIL (28일차)

C++

9번 문제 회고

애너그램 판별하는 코드를 작성해보았다.

#include <iostream>
#include <string>

using namespace std;

//두 문자열의 길이가 다르면 -1을 반환합니다.

int getMinChangesToAnagram(const string& s1, const string& s2) {
    // 여기에 답안을 작성해주세요.

    if (s1.length() != s2.length()) //두 문자열의 길이가 다르면 -1을 반환합니다.
    {
        return -1;
    }

    //결국 두 문자열을 비교해서 문자열의 각 알파벳을 비교해서 알파벳이 다 같으면 변경이 없어서 0
    //차이나는 그 만큼 변경횟수가 1씩 증가 
    int change = 0;
    string temp_s2 = s2;

    for (int n = 0; n < s1.length(); n++)
    {
        size_t pos = temp_s2.find(s1[n]);//같은 알파벳 위치를 찾음
        if (pos != string::npos) //찾았다면
        {
            //있는거니까 삭제 시키기
            temp_s2.erase(pos, 1);
        }
        else //다 돌았는데 같은게 없으니 변경해야하는 횟수다
        {
            change++;
        }
    }

    return change;
}

내가 작성한 코드지만 이중 for문으로 만들어서 속도가 느린편 입니다.

더 좋은 코드가 뭐가 있을지 AI의 도움을 받았습니다.

int getMinChangesToAnagram(const string& s1, const string& s2) {
    
    if (s1.length() != s2.length()) {
        return -1;
    }

    // ASCII 문자 전체를 커버하는 배열 (소문자만 있다면 26으로 최적화 가능)
    int charCount[256] = {0}; 
    
    // s1의 문자는 빈도수를 1 증가시키고, s2의 문자는 1 감소시킵니다.
    for (int i = 0; i < s1.length(); i++) {
        charCount[s1[i]]++;
        charCount[s2[i]]--;
    }

    int change = 0;
    
    // 빈도수 배열을 확인하여 양수인 값만 더합니다.
    for (int i = 0; i < 256; i++) {
        if (charCount[i] > 0) {
            change += charCount[i];
        }
    }

    return change;
}

저와 Ai코드를 분석해보니 차이점이 있었습니다.

가장 큰 차이는 사람의 사고방식과 컴퓨터가 일하기 편한 방식의 차이라고 합니다.

즉 문자열을 직접 조작하느냐, 데이터의 통계(개수)만 내느냐입니다.

내가 작성한 코드 (직접 조작 방식)

1. s1의 알파벳을 하나 집어 듭니다.
2. s2 전체를 뒤져서(find) 그 알파벳을 찾습니다.
3. 찾았다면 그 알파벳을 s2에서 지웁니다(erase). 지운 빈자리를 메꾸기 위해 뒤에 있는 알파벳들이 앞으로 한 칸씩 다 이동해야 합니다.
   • 문제점: find로 찾는 데 시간($O(N)$)이 걸리고, erase로 지우고 문자열을 당겨오는 데 또 시간($O(N)$)이 걸립니다. 이걸 문자열 길이만큼 반복하니 속도가 매우 느려집니다($O(N^2)$).

개선된 코드 (빈도수 계산 방식)

1. 각 알파벳이 몇 번 나왔는지 기록할 ‘장부(배열)’를 하나 만듭니다.
2. 문자열을 한 번만 쭉 읽으면서 s1에 있는 알파벳은 장부에 +1, s2에 있는 알파벳은 장부에 -1을 적습니다.
   • 장점: 문자열을 찾거나 지우고 이동시키는 과정이 아예 없습니다. 그저 장부의 숫자만 올리고 내리면 되기 때문에 컴퓨터 입장에서 계산이 엄청나게 빠릅니다($O(N)$).

문제를 접근한 사고 과정

코딩 테스트에서 이런 문자열 비교 문제를 만났을 때, 다음과 같은 흐름으로 문제를 쪼개어 생각해야 합니다.

STEP 1: 문제의 본질 파악하기

“아나그램(Anagram)을 만들려면 순서는 상관없고, 알파벳의 종류와 개수만 똑같으면 되는구나!”

순서가 중요하지 않다는 것을 깨닫는 것이 핵심입니다. 굳이 두 문자열의 위치를 하나하나 대조할 필요가 없다는 뜻입니다.

STEP 2: 효율적인 비교 방법 떠올리기 (과일 바구니 비유)

두 개의 과일 바구니(s1, s2)가 똑같은지 비교한다고 상상해 봅니다.

• 비효율적인 방법 (직접 조작): A 바구니에서 사과를 하나 꺼내고, B 바구니를 다 뒤져서 사과를 찾아 같이 버린다.
• 효율적인 방법 (통계): A 바구니에 사과 3개, B 바구니에 사과 1개가 있다는 걸 각각 세어둔다. 그러면 굳이 과일을 꺼내서 버리지 않아도, “사과 2개가 차이 나네!”라고 바로 알 수 있다.

STEP 3: 코드로 구현할 자료구조 선택하기

알파벳의 개수를 세기 위해 가장 빠른 방법은 무엇일까요? 해시맵(unordered_map)을 쓸 수도 있지만, 알파벳은 기껏해야 ASCII 코드(0~255) 안에 다 들어옵니다. 따라서 크기가 256인 단순한 고정 배열(Array)을 사용하는 것이 메모리도 적게 먹고 속도도 가장 빠르다고 판단했습니다.

STEP 4: 정답 도출의 규칙 찾기

개수를 다 세고 났을 때, 변경해야 할 최소 횟수를 어떻게 구할지 고민했습니다. 예를 들어 abc 와 abd를 배열에 +1, -1로 기록하면 아래와 같이 남습니다.

• a: 0 (상쇄됨)
• b: 0 (상쇄됨)
• c: +1 (s1에는 있는데 s2에는 없음 ➡️ 바꿔야 할 문자)
• d: -1 (s2에만 쓸데없이 있음 ➡️ 어차피 c를 위해 다른 문자로 덮어씌워질 문자)

결론

결국 마이너스 값은 신경 쓸 필요 없이, 플러스 값으로 남은 개수만 싹 더해주면 그것이 곧 내가 억지로 바꿔야 하는 문자의 개수(정답)가 됩니다.