[SWEA] 1928. Base64 Decoder

✍️ 문제 요약

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PR4DKAG0DFAUq&categoryId=AV5PR4DKAG0DFAUq&categoryType=CODE

SW Expert Academy

 

입력으로 Base65 Encoding 된 String이 주어졌을 때, 해당 String을 Decoding 하여 원문을 출력하라.

 

Encoding 방법

🧐 문제 해석

문제만 읽어서는 인코딩하는 방법이 잘 와닿지 않았다.

문제의 댓글을 힌트삼아 그 방법을 알아냈다.

 

인코딩 하는 방법

예를 들어, 원문이 `Life itself is a quotation.`이라고 가정하자.

 

이제 한 글자씩 아스키코드를 구한 뒤, 이를 이진수로 바꾼다.

L -> L은 아스키코드 76이다. 그리고 76을 이진수로 바꾸면 `01001100`이다.

i -> i는 아스키코드 105이다. 그리고 105를 이진수로 바꾸면 `01101001`이다.

.

.

.

 

위에서 구한 이진수를 한 줄로 이어붙인다.

그럼 `0100110001101001 ...`가 될것이다.

 

이제 위 문자열을 6bit 씩 쪼갠 뒤, 이를 다시 십진수로 바꾸어 표에 대응하는 문자를 찾는다.

6bit 씩 쪼개면 `010011` `000110` `1001 ...` 이 된다.

 

`010011`은 십진수 19이고, 표에서 19에 대응하는 값은 `T`이다.

`000110`은 십진수 6이고, 표에서 6에 대응하는 값은 `G`이다.

 

이런식으로, `Life itself is a quotation.`가 인코딩되어 `TG ...`가 되는 것이다.

 

❗️ 우리는 원문을 인코딩 하는 것이 아니라, 인코딩 된 문자열을 "디코딩" 해야한다.

인코딩 하는 방법을 이해했으면, 이를 기반으로 디코딩 하는 방법을 유추해보자.

 

디코딩 하는 방법

예를 들어, 디코딩 된 문자열이 `TG ...`라고 가정하자.

인코딩과 반대로 진행하면 된다.

 

T -> 표에 대응하는 값 19 -> 19의 이진수 `010011` (⭐️ 이 때 이진수는 6bit로 만들어야 한다!)

G -> 표에 대응하는 값 6 -> 6의 이진수 `000110`

.

.

.

 

이진수를 6bit로 만들어야 하는 이유는, 인코딩 할 때 6bit씩 쪼갰기 때문이다. (파이썬에서는 `zfill()`을 이용하여 원하는 만큼 0으로 채울 수 있다.)

그리고 이를 한 줄로 이어붙인다. 그럼 `010011000110 ...`가 될것이다.

 

이제 위 문자열을 8bit(=1byte) 씩 쪼갠 뒤, 이를 다시 십진수로 바꾸어 아스키코드에 대응하는 문자를 찾는다.

8bit 씩 쪼개면 `01001100` `0110 ...` 이 된다.

 

`01001100`은 십진수 76이고, 아스키코드에서 76은 `L`이다.

 

이런식으로, `TG ...`가 디코딩되어 `L ...`가 되는 것이다. (답은 `Life itself is a quotation.`이겠지..)

 

✨ 나의 풀이

나는 `lst`와 `dic`을 모두 선언했는데, `lst`만 선언하고자 한다면 `binary = format(dic[x], 'b')` 부분을 `binary = format(lst.index(x), 'b')`로 변경하여 같은 답을 얻을 수 있다.

 

🙋‍♀️ 하지만 `index()` 메서드는 리스트에서 특정 값의 인덱스를 반환하기 위해 리스트 전체를 탐색해야 하므로 시간복잡도가 `O(n)`이다. 반면 딕셔너리는 `O(1)`의 시간복잡도로 접근할 수 있으므로, 매번 `index()`를 호출하여 인덱스를 구하는 것보다 더 효율적이라고 생각했다. 

import sys
from collections import defaultdict
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")

if __name__ == '__main__':
    T = int(input())

    lst = [
        'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
        'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
        '0','1','2','3','4','5','6','7','8','9','+','/'
    ]
    dic = {val : idx for idx, val in enumerate(lst)}

    for test_case in range(1, T+1):
        S = input()
        print('#{}'.format(test_case), end=' ')

        buffer = ''
        for x in S:
            binary = format(dic[x], 'b')
            buffer += binary.zfill(6) # 앞에 0을 채워서 6bit 로

        ans = ''
        for i in range(0, len(buffer), 8):
            decimal = int(buffer[i:i+8], 2) # 8bit 씩 묶어서 2진수를 10진수로 변환
            print(chr(decimal), end='') # 10진수를 아스키코드로 변환
        print()