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

둘만의 암호

문제 링크

둘만의 암호

분석

s의 각 알파벳을 index만큼 뒤에 오는 알파벳으로 변경해야 합니다.
이때 변경 시 중간에 skip에 해당하는 알파벳은 추가로 건너뜁니다.

알파벳을 바꾸면서 z를 넘어갈 경우 a로 돌아와야합니다.

알파벳 소문자로만 이루어져 있으므로, 대소문자 구분은 필요 없습니다.

풀이

#include <string>
#include <unordered_set>

using namespace std;

string solution(string s, string skip, int index) {
    string answer = "";
    
    // 스킵해야하는 문자 저장
    unordered_set<char> skipSet(skip.begin(), skip.end());
        
    // s를 순회
    for (char curChar : s)
    {
        // 현재 알파벳을 바꾼 횟수
        int count = 0;
        
        // 알파벳을 index번 까지만 바꾼다.
        while (count < index)
        {
            // 현재 알파벳을 1만큼 뒤로 바꾸기
            ++curChar;
            
            // 현재 알파벳이 z보다 크다면 a로 순환
            if (curChar > 'z')
            {
                curChar = 'a';
            }
            
            // 현재 알파벳이 스킵해야하는 단어가 아닐 경우
            if (skipSet.find(curChar) == skipSet.end())
            {
                ++count;
            }
        }
        
        // 결과 값 저장
        answer += curChar;
    }
    
    return answer;
}

unordered_set<char>을 사용해서 스킵해야하는 문자를 빠르게 조회합니다.

성능 요약

시간 복잡도는 $O(n \times m \times p)$입니다.

• skipSet을 생성 시 skip의 길이만큼 반복하지만, 알파벳은 최대 26개 $O(26) \approx O(1)$
  • 문제의 경우 알파벳은 최대 10개
• s를 순회하는 반복문 $O(n)$
• index번 문자 변환 $O(i)$
• unordered_set.find는 평균적으로 $O(1), 최악의 경우 $O(m)$
• $O(1) + O(n) \times O(i) \times O(m)$
• $O(n \times i \times m)$

공간 복잡도는 $O(n)$입니다.

• skipSet은 알파벳의 개수인 최대 26개 저장 $O(26) \approx O(1)$
• answer은 반환할 문자열을 저장 s의 길이만큼 $O(n)$
• $O(1) + O(n)$
• $O(n)$

테스트 1 〉 통과 (0.02ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 3.66MB)
테스트 3 〉 통과 (0.04ms, 3.68MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.02ms, 4.2MB)
테스트 6 〉 통과 (0.02ms, 3.59MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 3.72MB)
테스트 9 〉 통과 (0.02ms, 3.64MB)
테스트 10 〉 통과 (0.02ms, 4.14MB)
테스트 11 〉 통과 (0.02ms, 4.2MB)
테스트 12 〉 통과 (0.02ms, 4.21MB)
테스트 13 〉 통과 (0.02ms, 4.13MB)
테스트 14 〉 통과 (0.01ms, 3.65MB)
테스트 15 〉 통과 (0.01ms, 3.67MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)
테스트 17 〉 통과 (0.02ms, 4.22MB)
테스트 18 〉 통과 (0.02ms, 3.64MB)
테스트 19 〉 통과 (0.03ms, 3.67MB)