SWEA_1242_암호코드 스캔

너무 어려워...

문제를 보고 든 생각

• 어제 푼 문제랑 똑같은 거 아닌가?

  No...

• 오늘도 뒤에서부터 탐색해야겠다.

통과하지 못한 코드🤐

접근 방식

1. 주어진 배열에서 암호코드를 뽑아내자
2. 암호코드를 2진수 형태로 변환하자
3. 2진수 형태의 암호코드를 해석하자

코드를 작성하며 든 생각

1. 10진수를 2진수로 바꾸는 방법이 뭐였더라

   • 2진수 변환시 최대 자리수가 얼마인가?

     16진수를 변환하는 것이었기에 최대 숫자가 15임을 알 수 있고, 이는 길이가 4인 2진수로 표현이 가능하다.

   • 2로 나누며, 나머지를 뒤에서부터 넣는 것!

   def decimal_to_binary(n):
       result = [0] * 4
       for i in range(3, -1, -1):
           result[i] = n % 2
           # 2로 나눈 몫을 이용해 다음 계산을 진행한다.
           n //= 2
       return result

2. 암호코드를 탐색할 때에는 뒤에서부터 탐색하는 게 좋겠다.

   암호배열이 0으로 초기화되어있고, 암호의 맨 뒷자리는 반드시 1로 끝나는 것을 고려하였을 때
   뒤에서부터 탐색하는 것이 가장 쉬울 것이라는 생각이 들었다.

3. 암호코드가 중복되는 게 많으니 무의미한 반복 연산을 피하기 위해 중복을 제거하면 좋겠다.

   hex_code_list = list(set(hex_code_list))

4. 암호패턴이 4자리로 되어 있는데, 뒤에 3자리만 알아도 암호를 구분할 수 있다.

5. 코드가 점점 누더기가 되어간다...

import sys

sys.stdin = open("암호코드 스캔.txt")

# code pattern dict
# 비율을 숫자로, 배수로 곱하더라도 유일한 값을 나타낼 것
pattern_dict = {
    "3211": "0",
    "2221": "1",
    "2122": "2",
    "1411": "3",
    "1132": "4",
    "1231": "5",
    "1114": "6",
    "1312": "7",
    "1213": "8",
    "3112": "9",
}

# 16진수를 10진수로 변환
def hex_to_decimal(n):
    if ord("A") <= ord(n):
        return ord(n) - ord("A") + 10
    else:
        return ord(n) - ord("0")

def decimal_to_binary(n):
    # n의 최대값은 15
    result = [""] * 4
    for idx in range(3, -1, -1):
        result[idx] = str(n % 2)
        n //= 2
    return "".join(result)


def decoding(dc, code):
    # 뒤에 3자리를 비교
    code_count_set_to_int = int(code[1:])
    m = 1
    while code:
        for pattern in pattern_dict.keys():
            sliced_pattern = pattern[1:]
            if code_count_set_to_int == (m * int(sliced_pattern)):
                dc = pattern_dict[pattern] + dc
                code = ""
                break
        m += 1
    return dc, ""

T = int(input())

for tc in range(1, T + 1):
    # N: 배열의 세로 크기
    # M: 배열의 가로 크기
    N, M = map(int, input().split())

    data = [input() for _ in range(N)]

    # 암호코드가 있는 부분을 찾아보자
    # 1. 암호코드를 탐색하여, 암호 문자열을 담기
    code_list = []
    for r in range(N):
        code_cart = ""
        cart_open = False
        for c in range(M - 1, -1, -1):
            if data[r][c] != "0":
                code_list.append(data[r][:c + 1])
                break
            continue
    # 중복된 code 제거
    code_list = list(set(code_list))
    # print(code_list)

    # 16진수의 code를 2진수의 code로 변환
    binary_code_list = []
    for hex_code in code_list:
        binary_code = ""
        for code_t_hex in hex_code:
            code_t_decimal = hex_to_decimal(code_t_hex)
            code_t_binary = decimal_to_binary(code_t_decimal)
            binary_code += code_t_binary
        # 모든 이진 암호의 오른쪽은 1로 끝나기 때문에 가장 우측 0을 제거한다.
        binary_code_list.append(binary_code.rstrip("0"))
    # print(binary_code_list)

    # 코드 해석
    # 코드는 오른쪽부터 해석한다.
    # 위쪽의 코드와 합쳐도 됨
    decode_list = []
    for binary_code in binary_code_list:
        code_count_set = []
        code_count = 0
        before_code = "1"
        decode = ""
        for i in range(len(binary_code) - 1, -1, -1):
            current_code = binary_code[i]
            # 이전 코드와 같은 경우
            if before_code == current_code:
                code_count += 1
                continue
            # 보고 있던 코드와 다른 경우
            if before_code != current_code:
                code_count_set = [code_count] + code_count_set
                before_code = current_code
                code_count = 1
            if len(code_count_set) == 4:
                # 뒤에 3자리를 비교
                decode, code_count_set = decoding(decode, code_count_set)
            if len(decode) > 8:
                break
        else:
            if len(code_count_set) < 3 and code_count != 0:
                code_count_set = str(code_count) + code_count_set
            if len(decode) == 7:
                code_count_set = "1" + code_count_set
                decode, code_count_set = decoding(decode, code_count_set)
            decode_list.append(list(map(int, decode)))
    # print(decode_list)

    # 검증
    result = 0
    for decode in decode_list:
        if ((decode[0] + decode[2] + decode[4] + decode[6]) * 3 + decode[1] + decode[3] + decode[5] + decode[7]) % 10 == 0:
            result += sum(decode)
    print(f"#{tc} {result}")

통과한 코드🥵

살릴 수 있는 개념은 살리되, 다시 작성하기로 하였다.

변경사항

1. 16진수를 2진수로 변환할 때, 굳이 함수를 거치지 않아도 된다.

   0 ~ F까지 총 16개의 수가 있는데, 이걸 딕셔너리 형태로 정리해두고 사용하는 게 더 깔끔하다는 생각이 들었다.

   물론, 변경 방법은 꼭 알고 있어야겠지.

2. 암호패턴

   4자리의 암호패턴 중에서 뒤에 3자리만 있으면 구분이 가능하다는 것을 확인했고, 나는 다음과 같은 방식으로 비교하였다.

   code_count_set_to_int = int(code[1:])
   m = 1
   while code:
       for pattern in pattern_dict.keys():
           sliced_pattern = pattern[1:]
           if code_count_set_to_int == (m * int(sliced_pattern)):
               dc = pattern_dict[pattern] + dc
               code = ""
               break
   	m += 1

• 4자리까지 구한 뒤에 3자리만 가지고 암호 해독을 진행

• 비율이 늘어나는 것을 고려하여, 일치하는 암호 키를 찾을 수 없을 때에는 m을 곱해주었다.

  여기에서 생기는 문제점

1. 암호패턴의 비율이 커지면서 두자리 수가 되었을 때, 총 5자리수가 넘어옴

2. 한 행의 마지막 암호가 4자리를 채우지 못하고 3자리로 끝나버렸을 때, 별도의 조건을 따로 작성하여야 함

   해결방법

• 암호패턴을 3자리까지만 찾은 뒤, 4번째 자리를 탐색시작할 때 바로 패턴 확인 작업을 한다.

• 비율이 증가하는 것을 고려하여, 최소 공배수로 나누어 준다.

  min(b, c, d)

3. 동일한 암호 패턴의 중복 피하기

   배열에 암호가 여러 줄 반복적으로 등장하다보니, 앞에서 중복 제거를 거쳤음에도 다 제거되지 않는 경우가 있었다.

   이번에도 set을 사용해서 중복을 제거하려고 했지만, 2차원 배열은 set을 사용할 수 없었다.

   해독 문자들을 배열에서 문자열로 바꿔준 뒤에 ([str, str, ...]) set을 사용해도 되겠지만, 다른 멋진 분들의 코드를 참고하여 visited 배열을 따로 만들어주기로 하였다.

   visited = []
   # ...
   if len(decode) == 8:
       if ((decode[0] + decode[2] + decode[4] + decode[6]) * 3 + decode[1] + decode[3] + decode[5] + decode[7]) % 10 == 0:
           if decode not in visited:
               result += sum(decode)
               visited.append(decode)
           decode = []

배열도 in 연산자를 이용할 수 있다는 것을 알게되었다.

T = int(input())

hex_to_bin = {
    '0':'0000', '1':'0001', '2':'0010', '3':'0011',
    '4':'0100', '5':'0101', '6':'0110', '7':'0111',
    '8':'1000', '9':'1001', 'A':'1010', 'B':'1011',
    'C':'1100', 'D':'1101', 'E':'1110', 'F':'1111'
}

pattern_dict = {
    "211": 0,
    "221": 1,
    "122": 2,
    "411": 3,
    "132": 4,
    "231": 5,
    "114": 6,
    "312": 7,
    "213": 8,
    "112": 9,
}

for tc in range(1, T + 1):
    # N: 배열의 세로 크기
    # M: 배열의 가로 크기
    N, M = map(int, input().split())
    data = [input() for _ in range(N)]

    # 열 중복 제거
    data_set = list(set(data))
    N2 = len(data_set)

    data_to_binary = [""] * N2
    for i in range(N2):
        for j in range(M):
            data_to_binary[i] += hex_to_bin[data_set[i][j]]

    # 0으로만 이루어진 행 제거
    clean_data_to_binary = []
    for x in data_to_binary:
        if int(x) != 0:
            clean_data_to_binary.append(x)

    result = 0
    visited = []
    for binary_code in clean_data_to_binary:
        decode = []
        # 암호 비율
        a = b = c = d = 0
        binary_code = binary_code.rstrip("0")
        L = len(binary_code)
        for i in range(L - 1, -1, -1):
            if c == 0 and binary_code[i] == "1":
                d += 1
            # d > 0 조건이 없으면, a 자리에서 읽어야 할 "0"을 자기가 읽어버린다.
            elif d > 0 and b == 0 and binary_code[i] == "0":
                c += 1
            elif a == 0 and binary_code[i] == "1":
                b += 1
            elif b > 0 and c > 0 and d > 0 and binary_code[i] == "0":
                # 뒤에 3자리만 고려하여도 구분이 가능함
                # 비율 고려
                div = min(b, c, d)
                b //= div
                c //= div
                d //= div
                key = str(b) + str(c) + str(d)
                decode = [pattern_dict[key]] + decode
                a = b = c = d = 0

            if len(decode) == 8:
                if ((decode[0] + decode[2] + decode[4] + decode[6]) * 3 + decode[1] + decode[3] + decode[5] + decode[7]) % 10 == 0:
                    if decode not in visited:
                        result += sum(decode)
                        visited.append(decode)
                decode = []
    print(f"#{tc} {result}")

---

오늘 알게 된 내용😜

1. 배열도 in연산자를 쓸 수 있구나
2. 곱하는 게 어려우면, 나눠보자
3. 딕셔너리도 활용되는 경우가 많구나
4. 아니다 싶으면 코드를 다시 작성해보자