HackerRank의 Caesar Cipher 문제를 함께 풀어보도록 하겠습니다.
문제
문자열 s와 숫자 k가 주어졌을 때, 문자열 내의 모든 알파벳 대소문자를 k만큼 돌려서 반환해라.
단, 문자를 돌리다가 알파벳의 마지막 문자인 Z나 z에 다다르면 다시 알파벳의 첫 문자인 A나 a로 돌아오면 된다.
그리고 알파벳 문자 외의 숫자나 특수 기호 등은 그대로 두면 된다.
예제
- 입력
s: wX5%yA
k: 2- 출력
zA5%bD풀이 1
이 문제를 푸는 가장 단순무식한 방법은 문제에 나온데로 모든 문자의 유니코드 값을 k번 증가시키는 것입니다.
여기서 조심할 케이스는 알파벳의 마지막 문자인 Z나 z로써 알파벳의 첫 문자인 A나 a로 돌아와주도록 처리를 해야합니다.
이 간단한 알고리즘을 코드로 구현하면 다음과 같습니다.
def caesarCipher(s, k):
output = []
for ch in s:
if ch.isupper():
num = ord(ch)
for _ in range(k):
if num == ord("Z"):
num = ord("A")
else:
num += 1
output.append(chr(num))
elif ch.islower():
num = ord(ch)
for _ in range(k):
if num == ord("z"):
num = ord("a")
else:
num += 1
output.append(chr(num))
else:
output.append(ch)
return "".join(output)이 풀이는 이중 루프를 사용하는데 바깥 루프는 문자열 길이 만큼 반복하고, 안쪽 루프는 k만큼 반복을 합니다.
따라서 시간 복잡도는 O(sk)가 되며, 공간복잡도는 돌린 문자들을 저장을 위해서 배열을 사용하고 있어서 O(s)입니다.
풀이 2
위 풀이의 치명적인 단점은 성능이 문자열의 길이뿐만 아니라 k에 의해서도 좌우된다는 것입니다.
예를 들어, 엄청나게 큰 수가 k로 입력된다면 알고리즘의 실행 속도가 현저하게 떨어질 것입니다.
여기서 스스로에게 물어볼만 한 질문은 “과연 k가 100일 때, 각 문자를 100번 돌려야할까?” 입니다.
사실 머리를 조금 굴려보면 22번만 돌려도 100번 돌릴 것과 동일한 효과를 낼 수 있다는 것을 깨닫게 됩니다.
왜냐하면 영어에서 알파벳의 대문자와 소문자의 개수는 26개로 정해져있잖아요? 따라서 26번의 배수로 알파벳 문자를 돌리면 원래 문자로 돌아오게 됩니다. 결국, 1번을 돌리든, 27(= 26 + 1)번을 돌리든, 53(= 26 + 26 + 1)번을 돌리든 결과는 동일합니다.
이 사실을 활용해서 내부 루프를 k를 26으로 나눈 나머지만큼만 반복하도록 위 코드를 아주 살짝 수정하였습니다.
def caesarCipher(s, k):
output = []
for ch in s:
if ch.isupper():
num = ord(ch)
for _ in range(k % 26):
if num == ord("Z"):
num = ord("A")
else:
num += 1
output.append(chr(num))
elif ch.islower():
num = ord(ch)
for _ in range(k % 26):
if num == ord("z"):
num = ord("a")
else:
num += 1
output.append(chr(num))
else:
output.append(ch)
return "".join(output)아주 살짝 코드를 고쳤지만 이 알고리즘의 시간 복잡도는 O(s)로 향상됩니다.
왜냐하면 k가 최대 26이 되기 때문에 O(26 * 2 * s)는 빅오 표기법으로 결국 O(s)와 동일하기 때문입니다.
풀이 3
혹시 위 풀이에서 아쉬운 부분이 있으신가요?
저는 개인적으로 유니코드 값을 for 문을 이용해서 1씩 더해주는 부분이 불만족스럽습니다.
그냥 간단하데 k를 더해버리면 안될까요❓
앗❗ 그러면 알파벳의 마지막 문자인 Z나 z의 유니코드 값을 넘어가버리는 불상사가 생길 수가 있겠네요… 😞
문자의 유니코드 값이 알파벳의 범위를 넘어가는 경우를 예방할 수 있는 방법은 없을까요? 수학적으로 생각을 해보시면 아래 두 개의 공식을 얻으실 수 있으실 것입니다.
(대문자의 유니코드 값 - `A`의 유니코드 값 + k) % 26 + `A`의 유니코드 값(소문자의 유니코드 값 - `a`의 유니코드 값 + k) % 26 + `a`의 유니코드 값이게 무슨 말인지 문자열 Y와 k가 3가 주어진 초간단한 경우를 생각해볼까요?
당연히 원하는 결과는 B 겠죠?
Y의 유니코드 값은 89인데, 우리는 89 + 3 = 92 대신에 B의 유니코드 값인 66가 되기를 원합니다.
Y의 유니코드 값에서 A의 유니코드의 값을 빼면, 89 - 65 = 24가 되는데요.
여기에 k 값인 3을 더하면 24 + 3 = 27이 되네요.
이 값을 26으로 나눈 나머지는 27 % 26 = 1 입니다.
여기서 A의 유니코드 값인 65을 더하면 1 + 65 = 66가 됩니다.
결국 B의 유니코드 값을 얻게 되었습니다. 🤗
이 공식의 토대로 코드를 작성해보겠습니다.
def caesarCipher(s, k):
output = []
for ch in s:
if ch.isupper():
output.append(chr((ord(ch) - ord("A") + k) % 26 + ord("A")))
elif ch.islower():
output.append(chr((ord(ch) - ord("a") + k) % 26 + ord("a")))
else:
output.append(ch)
return "".join(output)이 풀이의 시간 복잡도는 이전 풀이 대비 빅오 계산법 기준으로는 차이가 없습니다. 하지만 문자 하나를 돌리는데 소요되는 최대 연산량을 26회에서 1회로 줄였기 때문에 충분히 면접관에게 어필할 수 있는 최적화일 것입니다.
마치면서
이렇게 비교적 쉬운 문제도 다양한 방법으로 접근해보는 연습을 해두시면 분명 코딩 시험 때 큰 도움이 될 것 같습니다.