[HackerRank 풀이/python] Cipher (medium)

문제 설명: 친구 사이인 Jack 과 Daniel 은 대화 내역을 탐정 기관에 도청 당하지 않기 위해 암호화를 하고자 했고, 결국 새로운 암호법을 만들어냈다. 모든 메시지 b 는 이진수 표현(binary representation) 으로 인코딩 하고, 이를 0, 1, ..., k-1 비트만큼씩 이동(shift) 시켜 k 번을 쓴다. 각 열(column) 을 XOR 연산* 처리하면 최종적으로 인코딩된 문자열을 얻게 된다.

(*XOR 연산: 이진수 값의 각 자리수를 비교해서 같으면 0, 다르면 1 을 계산하는 비트 연산자)

만약 b = 1001011 , k = 4 인 경우의 예시는 아래와 같다:

이제 우리는 메시지를 해독(decode) 해야 한다. (설명 중략) 이런 식으로 인코딩된 메시지 s 와 키 k 가 Daniel 에게 보내진다.

Jack 은 이 인코딩 알고리즘을 이용했고, Daniel 에게 디코딩 알고리즘을 구현하라고 했다. Daniel 을 도와주자!

 

제한 조건:

• 1 <= n <= 10^6  &  1 <= k <= 10^6
• |s| = n + k - 1  ,  s 는 valid 한 문자열임이 보장됨

 

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

 

[풀이 1안]

• 접근법
  • 구조적으로, 디코딩 완료된 문자열 b 의 첫번째 / 마지막 문자는 인코딩된 문자열 s 의 첫번째 / 마지막 문자와 동일하므로, 이를 제외한 나머지 문자들만 구하면 됨
  • 문자열의 뒤에서부터 디코딩해나간다고 하면, b 의 뒤에서 i 번째 문자는 '직전 (k-1) 개 문자 ref' 와 's 의 뒤에서 i 번째 문자' 정보를 활용하여 구할 수 있음
    • 직전 (k-1) 개 문자 ref 와 s 의 뒤에서 i 번째 문자에 대해 XOR 연산을 한 결과  ==  b 의 뒤에서 i 번째 문자!
    • i 가 업데이트 됨에 따라 ref 도 업데이트 되어야 하며, 먼저 들어온 값이 먼저 나가게 되므로 queue 구조 활용 

 

• 코드 구현

from collections import deque

def cipher(k,s):
    n = len(s) - k + 1
    b = [0] * n
    b[0], b[-1] = s[0], s[-1]
    ref = deque([int(s[-1])])
    ref_sum = int(s[-1])
    l = len(s) - 1

    for i in range(1, n-1):
        if (s[l-i] == '1' and ref_sum%2 == 1) or (s[l-i] == '0' and ref_sum%2 == 0):
            b[n-1-i] = '0'
            ref.append(0)
        else:
            b[n-1-i] = '1'
            ref.append(1)
            ref_sum += 1

        if len(ref) > (k-1):
            diff = ref.popleft()
            ref_sum -= diff
            
    res = ''.join(b)
        
    return res

 

• 결과
  • 처음에는 ref_sum 변수를 안만들고 매 비교시에 sum(ref) 연산을 했더니 타임아웃 에러가 나는 케이스가 있었음
    • sum(ref) 연산 시 ref 리스트의 최대 길이 만큼 O(k-1) 시간이 걸리므로 결과적으로 O(n*(k-1)) 가 됨 ㅜ
    • 별도로 ref_sum 변수를 만들어 int 값으로 저장 / 업데이트 하도록 수정  -->  시간 복잡도 O(n) 
  • Bit Manipulation 항목에 있는 문제인 만큼 비트 연산자 (XOR == ^) 를 활용할 수도 있을 듯...!