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

A. 문제설명

 

두 문자열 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 함수를 완성해주세요.

B. 답안

def solution(s, skip, index):
    answer = []
    alphabets = list("abcdefghijklmnopqrstuvwxyz")

    for skip_ch in skip:
        alphabets.remove(skip_ch)

    for ch in s:
        answer.append(alphabets[(alphabets.index(ch)+index)%len(alphabets)])

    return ''.join(answer)

C. 개선

s의 길이가 짧고, skip의 길이 또한 짧기 때문에 알파벳 전체를 list화 하여 사용했다.

 

그러나 remove함수와 index함수 등 배열탐색 시간이 소모된다. 시간복잡도가 좋지 않고, 확장성에도 좋지 않다.

from string import ascii_lowercase

def solution(s, skip, index):
    result = ''

    a_to_z = set(ascii_lowercase)
    a_to_z -= set(skip)
    a_to_z = sorted(a_to_z)
    l = len(a_to_z)

    dic_alpha = {alpha:idx for idx, alpha in enumerate(a_to_z)}

    for i in s:
        result += a_to_z[(dic_alpha[i] + index) % l]

    return result

위와 같이 dict를 사용하여, 인덱스를 기록하면 시간복잡도가 감소한다..!

 

*추가로 list의 유용한 메소드

append()	Adds an element at the end of the list
clear()	Removes all the elements from the list
copy()	Returns a copy of the list
count()	Returns the number of elements with the specified value
extend()	Add the elements of a list (or any iterable), to the end of the current list
index()	Returns the index of the first element with the specified value
insert()	Adds an element at the specified position
pop()	Removes the element at the specified position
remove()	Removes the item with the specified value
reverse()	Reverses the order of the list
sort()	Sorts the list

 

출처:https://www.w3schools.com/python/python_lists_methods.asp