[프로그래머스] 둘만의 암호 (Python)

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

https://school.programmers.co.kr/learn/courses/30/lessons/155652

문제 설명

· 문자열 s의 각 알파벳을 index만큼 뒤의 알파벳으로 바꿔줌

· index만큼의 뒤의 알파벳이 z를 넘어갈 경우 다시 a로 돌아감

· skip에 있는 알파벳은 제외하고 건너뜀

정리하면 주어진 문자열의 각 알파벳을 index만큼 뒤에 위치한 알파벳으로 변경하되, skip에 있는 알파벳은 index를 세는 과정에 포함되지 않음

접근 방법

· 전체 알파벳에서 skip에 있는 알파벳을 뺀, 순회할 알파벳 배열 만들기

· 바꿔줄 문자의 알파벳 배열에서의 인덱스를 구한 뒤, index만큼 더하기

· index가 알파벳 배열의 길이보다 클 수 있으므로, 알파벳 길이로 나눈 나머지로 대체하기

· 바뀐 알파벳으로 이루어진 배열을 문자열로 만들어 반환하기

알고리즘 설계 및 구현

def solution(s, skip, index):
    # skip 탐색의 효율성을 위해 list -> set으로 변경
    skip_set = set(skip)
    alphabet = [c for c in "abcdefghijklmnopqrstuvwxyz" if c not in skip_set]
    
    # 미리 알파벳의 인덱스를 찾아서 Dict에 저장
    alphabet_index = {c: i for i, c in enumerate(alphabet)}
    
   
    # index만큼 뒤에 위치한 알파벳들의 배열을 구한 뒤 문자열로 변환하여 반환
    return ''.join(
        alphabet[(alphabet_index[c] + index) % len(alphabet)] 
        for c in s
    )

결과

최적화 및 개선 방안

skip_set = set(skip)
alphabet = [c for c in "abcdefghijklmnopqrstuvwxyz" if c not in skip_set]

· skip에 알파벳이 있는지 확인하는 과정에서, List에서 찾으면 O(n), Set에서 찾으면 O(1)이므로 skip_set 사용

alphabet_index = {c: i for i, c in enumerate(alphabet)} 
    return ''.join(
        alphabet[(alphabet_index[c] + index) % len(alphabet)] 
        for c in s
    )

· list.index를 통해 list comprehension 안에서 c의 위치를 찾을 경우 O(n**2)이 되므로, Dict에 인덱스 정보를 미리 저장해 줌으로써 O(n)으로 낮춤