프로그래머스 [연습문제 / 둘만의 암호](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 둘만의 암호

---

문제 링크: 문제 보기

문제 설명:

주어진 문자열 s의 각 문자를 index만큼 이동시켜 새로운 암호를 생성하는 문제입니다. 단, 특정 문자는 제외하고 이동해야 하므로 이를 고려하여 변환해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int skipAlpha[26]; // 제외할 알파벳 여부 저장

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

    // 제외할 알파벳을 기록
    for (char ch : skip) {
        skipAlpha[ch - 'a'] = 1;
    }

    // 문자열 변환
    for (char ch : s) {
        int idx = index;
        while (idx) {
            ch++;
            if (ch > 'z') ch = 'a'; // z 다음은 a로 순환
            if (skipAlpha[ch - 'a'] == 0) idx--; // 제외 문자가 아니면 감소
        }
        answer += ch;
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 알파벳을 일정 횟수만큼 이동하면서 제외 문자를 건너뛰고 새로운 문자열을 생성합니다.
• 구현 세부사항:
• 배열 skipAlpha를 사용하여 제외할 알파벳을 저장합니다.
• 각 문자에 대해 index 만큼 이동하는 동안 제외 문자는 건너뛰고 진행합니다.
• 알파벳이 'z'를 넘어가면 'a'로 순환하도록 처리합니다.
• 시간 복잡도 분석:
• 제외 문자 기록: O(k) (k는 skip 길이)
• 문자 변환: O(n * index) (n은 s 길이, index는 최대 이동 횟수)
• 총 시간 복잡도: O(n * index + k)

---

결과

이 코드는 주어진 문자열을 변환 규칙에 맞게 처리하며, 제외 문자를 고려하여 정확한 암호를 생성합니다.

다른 접근 방식으로는 vector를 사용해 미리 변환된 알파벳 테이블을 만들어서 더 빠르게 변환하는 방법이 있습니다.