[백준/Python] 11575번 Affine Cipher

 

https://www.acmicpc.net/problem/11575

11575번: Affine Cipher

문제분석 

주어진 문자열을 다음 규칙에 따라 암호화 한다.

a * (문자의 아스키코드) + b

z의 아스키코드값을 넘어가면 넘긴만큼 a부터 더한다.

 

문제풀이

각각의 아스키코드값을 변경해주고 26으로 나눠서 나머지 값을 계산하면 되는 간단한 문제이지만, 시간초과가 걸렸다.
다음은 시간초과가 나온 코드이다.

input = __import__('sys').stdin.readline

T = int(input().strip())
for t in range(T):
    a, b = map(int, input().strip().split())
    text = input()
    code = ''
    for c in text:
        num = (a * (ord(c)-ord('A')) + b )% 26
        code += chr(num+ord("A"))
    print(code)

바뀐 아스키코드 값(num)을 계산하고 해당하는 문자를 빈 문자열 code에 더해주었더니 시간초과가 출력되었다.
문자열의 길이가 최대 1,000,000이어서 최악의 1,000,000번 문자열의 크기를 바꿔야 할 수 있기때문에 시간초과가 난 것 같다. 
빈문자열에 계속 더하는 대신 원래있던 문자열을 바꾸는 코드로 바꾸었더니 해결 되었다.

input = __import__('sys').stdin.readline

T = int(input().strip())
for t in range(T):
    a, b = map(int, input().strip().split())
    text = list(input().strip())
    for i in range(len(text)):
        num = (a * (ord(text[i])-ord('A')) + b ) % 26
        text[i] = chr(num+ord("A"))
    print(''.join(text))
    
input = __import__('sys').stdin.readline