[HackerRank 풀이/python] Encryption (medium)

문제 설명: 다음과 같은 암호화 규칙에 따라 주어진 영문 텍스트를 암호화하시오.

우선, 텍스트에서 띄어쓰기(space) 를 모두 제거한 뒤, 이 텍스트의 길이를 L 이라고 한다. 그 후, 문자들(characters) 을 격자(grid) 형태로 적는다. 격자의 행과 열은 아래와 같은 제한을 따른다. 

예를 들어, 텍스트 s = 'if man was meant to stay on the ground god would have given us roots' 가 주어졌을 때, 띄어쓰기를 제거하면 문자열의 길이는 총 54자가 된다. sqrt(54) 는 7 과 8 사이의 수 이므로, 7행 8열인 격자 형태로 적으면 다음과 같다. 참고로, 복수의 격자가 행 x 열 >= L 을 만족해야 하며, 위의 조건을 만족한다면 전체 면적 (=행x열) 이 가장 작은 것을 선택한다. 

 

인코딩된 메시지는 각 열의 문자들을 띄어쓰기로 구분하여 차례로 나타낸 것과 같다. 위의 예시에서 인코딩된 메시지를 나타내면 다음과 같다: s' = 'imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau' 

이처럼 텍스트를 메시지로 인코딩 하는 함수를 작성하시오.

 

제한 조건:

• 1 <= 문자열 s 의 길이 <= 81
• s 는 ascii[a-z] 범위에 있는 문자와 띄어쓰기, ascii(32) 문자만을 포함

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 우선 주어진 제한 조건을 이용해서 행row, 열col 에 해당하는 숫자를 각각 구함
    • 기본적으로 sqrt(L) 값을 버림해서 얻은 정수를 row, 해당 row + 1 를 col 로 삼되,
    • L 이 어떤 수의 제곱수인 경우 ( sqrt(L) 이 int 인 경우 )  -->  row = col
    • row * col < L 인 경우 row 도 row+1 를 해서 row * col >= L 을 만족하도록 만듦
  • 이중 리스트를 이용해 matrix (~grid) 형태로 각 문자를 차례로 저장한 뒤, 인덱스 정보를 이용해서 최종적으로 인코딩 된 문자열을 리턴하면 완성
  • 코드를 짜고 보니 grid 형태로 저장하기 위해 활용한 div, mod 변수를 직접 활용해서 최종 문자열 인덱스를 표현할 수 있음을 확인함  -->  굳이 grid 형태로 데이터를 저장할 필요가 없으므로 주석 처리함!

 

• 코드 구현

def encrypt(s):
    row = int(len(s)**(1/2))
    if row**2 == len(s):
        col = row
    elif row * (row+1) < len(s):
        row += 1
        col = row
    else:
        col = row + 1

    #mat = [['']*col for _ in range(row)]
    enc = [''] * (row*col)
    for i, c in enumerate(s):
        div, mod = divmod(i, col)
        #mat[div][mod] = c
        
        idx = mod * row + div
        if (div == 0) and (mod > 0):
            c = ' ' + c
        enc[idx] = c

    return ''.join(enc)

 

• 결과
  • 무난히 통과...!
  • 이중 리스트를 이용해서 matrix / grid 형태를 표현하는 것에 익숙해지고 있는 것 같아 뿌듯 ~_~
  • 전체 시간 복잡도는 row, col 값을 구하는 데에 O(1) + 인코딩된 문자열로 바꾸는 데에 O(n) = O(n)