[프로그래머스/Day 21] 둘만의 암호 - 왜 내 코드는 'z'를 넘으면 터질까?

1. 문제 분석 및 핵심 조건

이 문제는 문자열 s의 각 알파벳을 뒤로 index만큼 미루어 암호를 만드는 문제입니다. 단순한 시저 암호와 달리 '제외할 문자(skip)'가 존재한다는 점이 핵심입니다.

• 제약 사항: 이동 과정에서 skip에 포함된 문자는 건너뛰어야 하며, 건너뛴 것은 이동 횟수에 포함되지 않습니다.
• 순환 구조: 알파벳이 'z'를 넘어가면 다시 'a'로 돌아가야 합니다.
• 주의할 점: 연속된 skip 문자가 있거나, 인덱스 끝부분에서 순환할 때 배열 인덱스 접근 오류(Segmentation Fault)가 발생하기 쉽습니다.

---

2. 초기 접근 및 시행착오

처음에는 skip 문자 개수를 미리 계산해서 한 번에 점프할 인덱스를 구하려고 했습니다.

• 시도했던 방식: current_index + index + skip_count와 같은 수식을 사용하여 최종 위치를 한 번에 계산한 뒤 배열에 접근했습니다.
• 문제 발생: signal: segmentation fault (core dumped) 오류가 발생했습니다.
• 원인 분석:
  • 배열 인덱스가 26을 넘어가는 경우에 대한 처리를 계산 이후에만 적용했습니다.
  • 계산 과정 중(index와 skip이 더해지는 시점)에 인덱스가 26을 초과하여, 유효하지 않은 메모리 공간을 참조하게 되었습니다.

---

3. 해결 전략

안전한 메모리 접근을 위해 "플래그(Flag) 배열"과 "단계별 시뮬레이션" 방식을 도입했습니다.

1. 플래그 배열 (Lookup Table):
   • 알파벳 개수(26)만큼의 vector를 생성하고, 모든 값을 1로 초기화합니다.
   • skip에 해당하는 문자만 0으로 표시하여, O(1) 시간에 스킵 여부를 확인할 수 있게 만듭니다.
2. 안전한 순회:
   • 한 번에 이동하려 하지 않고, 루프(while)를 통해 한 칸씩 이동합니다.
   • 이동할 때마다 offset을 증가시키되, 반드시 % ALPHABET_SIZE 연산을 수행하여 인덱스가 0~25 범위를 벗어나지 않도록 강제합니다.
3. 유효 이동 카운트:
   • 이동한 위치의 플래그가 1일 때만 유효한 이동(valid_count)으로 간주하여 카운트를 늘립니다.

---

4. 코드 구현

#include <string>
#include <vector>

using namespace std;

string solution(string s, string skip, int index) {
    string answer = "";
    constexpr int ALPHABET_SIZE = 26;

    // 1. 알파벳 개수만큼 vector를 1로 초기화한다.
    vector<int> alphabet_flags(ALPHABET_SIZE, 1);

    // 2. skip 알파벳에 해당하는 인덱스값을 0으로 설정한다.
    for (char skip_alphabet : skip)
    {
        alphabet_flags[skip_alphabet - 'a'] = 0;
    }

    // 3. s의 처음부터 끝까지 순회한다.
    for (char current_alphabet : s)
    {
        int current_alphabet_index = current_alphabet - 'a';

        // 4. 유효한 문자를 index개 만큼 찾을 때까지 한 칸씩 이동한다.
        int valid_count = 0; // 찾은 유효한 문자의 개수
        int offset = 0;      // 현재 위치에서 실제로 이동한 거리

        while (valid_count < index)
        {
            offset++;

            // 핵심: 이동할 때마다 모듈러 연산을 수행하여 SegFault 방지
            int check_index = (current_alphabet_index + offset) % ALPHABET_SIZE;

            if (alphabet_flags[check_index] == 1) {
                valid_count++;
            }
        }

        // 5. 최종적으로 이동한 위치를 이용해 문자를 구한다.
        int final_index = (current_alphabet_index + offset) % ALPHABET_SIZE;
        answer += 'a' + final_index;
    }

    return answer;
}

---

5. 복기 및 확장

이번 문제를 통해 배열 인덱스 접근 시점의 안전성이 얼마나 중요한지 깨달았습니다.

1. 안전한 인덱싱

초기 코드에서는 "나중에 % 연산을 하면 되겠지"라고 안일하게 생각했으나, 프로그램은 그 "나중"을 기다려주지 않고 메모리 오류를 뱉었습니다.

순환하는 자료구조(Ring Buffer 등)를 다룰 때는, 인덱스를 더하는 모든 순간에 경계값 처리(% Size)가 동반되어야 합니다.

2. 알고리즘의 확장

현재 작성한 코드는 check_index를 하나씩 확인하며 이동하는 시뮬레이션 방식입니다. 문제의 제약조건(index ≤ 20) 내에서는 충분히 빠르지만, 만약 index가 매우 크다면(예: 10억) 반복문이 길어질 수 있습니다.

이때는 다음과 같이 구조를 개선할 수도 있습니다.

• 아이디어: 구멍(skip)이 뚫린 배열을 건너뛰며 세는 대신, 애초에 구멍이 없는 유효 문자열을 만듭니다.
• 방법: vector 대신 string valid_chars = "acdef..." 처럼 유효한 문자만 모아둡니다.
• 효과: while 루프를 돌 필요 없이 (현재위치 + index) % 유효문자열길이 수식 하나로 O(1)에 이동할 위치를 찾을 수 있습니다.

이번에는 직관적인 이해를 위해 플래그 방식을 사용했지만, 데이터 규모가 커질 경우 데이터를 재가공하여 밀집된 형태로 만드는 것이 성능 최적화의 열쇠가 됨을 알 수 있었습니다.