[구름][알고리즘 먼데이][6주차] 제곱암호 : 파이썬(python)

 

 

구름  > 알고리즘먼데이챌린지 > 6주차 > 제곱암호

 

---

문제

 

 

 

✅ 풀이 과정

 

0. 알고리즘

- 문자열을 조건에 따라 변환하는 문제

 

1. 복잡도 고려

 

다시한번 파이썬의 연산시간을 알아보자

파이썬은 1초에 2000만 = 20,000,000 번 연산이 가능하다.

 

만약 시간제한이 1초, n = 100,000 (10만) 이라고 할 때

O(N^2) 으로 알고리즘을 짜게 되면

100000*100000   =  10,000,000,000 = 100억 번의 연산이 필요하므로, 시간초과가 나게 된다.

 

이 경우엔 O(NlogN) 으로 알고리즘을 짜야 1,600,000 번의 연산으로 수행 가능하다. (log 100,000 = 약 16)

 

일단 1초에 2천만이라는 걸 기억하고, 시간제한과 n을 고려하면 최대 가능한 알고리즘의 복잡도를 계산할 수 있다. 

 

 

이 문제에서는 n이 20만이고, 

암호문 길이 n <= 200000, (항상 짝수)

홀수인덱스, 짝수인덱스의 처리를 동시에 해주므로 n/2만큼만 반복한다. 

 

 

2. 수도코드

8 a1b2c3e4

 

1) 입력값의 분리

짝수와 홀수번째 index를 각각 문자와 숫자로 형변환 해준다.

2) 소문자 정보를 리스트로 저장

3) index 연산 후 %26을 해준다.

4) 최종 결과에 더해준다.

 

 

✅ 정답코드

import string
import sys
input = sys.stdin.readline 

alpha_small = list(string.ascii_lowercase)
n = int(input())
s = input().strip()

answer = ""
for i in range(0,n,2):
    character, num = s[i] , int(s[i+1])
    decryption = (alpha_small.index(character)+(num*num)) %26
    answer += alpha_small[decryption]

print(answer)

 

 

---

 

✅ 문제를 풀기 위해 새롭게 학습한 것

 

imports string을 통해 아스키코드의 lowercase와 uppercase를 가져올 수 있다는 것을 알았다. 

 

alpha_small = list(string.ascii_lowercase)
alpha_large = list(string.ascii_uppercase)

 

string에서 어떤 유용한것들이 있는지 더 알아봐야겠다.