프로그래머스/C++ 둘만의 암호

문제 설명

두 문자열 s와 skip, 그리고 자연수 index가 주어질 때, 다음 규칙에 따라 문자열을 만들려 합니다. 암호의 규칙은 다음과 같습니다.

• 문자열 s의 각 알파벳을 index만큼 뒤의 알파벳으로 바꿔줍니다.
• index만큼의 뒤의 알파벳이 z를 넘어갈 경우 다시 a로 돌아갑니다.
• skip에 있는 알파벳은 제외하고 건너뜁니다.

예를 들어 s = "aukks", skip = "wbqd", index = 5일 때, a에서 5만큼 뒤에 있는 알파벳은 f지만 [b, c, d, e, f]에서 'b'와 'd'는 skip에 포함되므로 세지 않습니다. 따라서 'b', 'd'를 제외하고 'a'에서 5만큼 뒤에 있는 알파벳은 [c, e, f, g, h] 순서에 의해 'h'가 됩니다. 나머지 "ukks" 또한 위 규칙대로 바꾸면 "appy"가 되며 결과는 "happy"가 됩니다.

두 문자열 s와 skip, 그리고 자연수 index가 매개변수로 주어질 때 위 규칙대로 s를 변환한 결과를 return하도록 solution 함수를 완성해주세요.

---

제한사항

• 5 ≤ s의 길이 ≤ 50
• 1 ≤ skip의 길이 ≤ 10
• s와 skip은 알파벳 소문자로만 이루어져 있습니다.
  • skip에 포함되는 알파벳은 s에 포함되지 않습니다.
• 1 ≤ index ≤ 20

---

입출력 예

s skip index result

"aukks"

"wbqd"

5

"happy"

---

입출력 예 설명

입출력 예 #1

본문 내용과 일치합니다.

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

string solution(string s, string skip, int index) {
    string answer = "";
    
    unordered_set<char> skip_set(skip.begin(), skip.end());
    
    for(char c : s){
        int steps = index;
        char current = c;
        
        while (steps > 0){
            current++;
            if(current > 'z'){
                current = 'a';
            }
            if(skip_set.find(current) == skip_set.end()){
                steps--;
            }
        }
        answer += current;
        
    }
    
    
    
    return answer;
}

unordered_set의 주요 특징

1. 중복을 허용하지 않음:
   • 집합(Set)처럼, 동일한 값을 여러 번 저장하지 않습니다.
   • 예: {a, b, c}에 a를 추가하려고 하면 무시됩니다.
2. 빠른 검색:
   • 내부적으로 해시 테이블을 사용하므로, 검색, 삽입, 삭제의 평균 시간 복잡도가 O(1)입니다.
   • O(1)O(1)
   • 정렬되지 않은 상태로 저장합니다. 따라서 순서가 중요하지 않은 경우 적합합니다.
3. 헤더 파일:
   • 사용하려면 **#include <unordered_set>*를 추가해야 합니다.

왜 unordered_set을 사용하는가?

1. 효율적인 검색:
   • skip_set.find(current):
     • current 문자가 skip에 있는지 확인합니다.
     • O(1)O(1)O(1) 복잡도로 빠르게 검색할 수 있습니다.
   • 예:
   • if (skip_set.find(current) == skip_set.end()) { // current 문자가 skip_set에 없는 경우 처리 }

skip_set의 동작

코드:

while (steps > 0) {
    current++; // 알파벳 이동
    if (current > 'z') {
        current = 'a'; // z를 넘어가면 다시 a로
    }
    if (skip_set.find(current) == skip_set.end()) {
        steps--; // skip에 없는 알파벳만 유효
    }
}

역할:

1. 현재 알파벳 current를 이동하면서 **skip_set*에 포함된 알파벳은 건너뜁니다.
2. skip_set.find(current) == skip_set.end():
   • current가 skip_set에 없는 경우(즉, 제외 대상이 아님)만 steps를 감소시킵니다.
3. steps가 0이 될 때까지 반복하여 최종 변환된 알파벳을 결정합니다.