Programming Advanced [S/W 문제해결 응용 구현01 시작하기] SWEA 1242 - 암호코드 스캔 (D5)

Problem

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15JEKKAM8CFAYD&categoryId=AV15JEKKAM8CFAYD&categoryType=CODE&problemTitle=1242&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

Solving

아이디어

1. 중복되는 가로줄은 삭제한다. (set으로 바꾸면 자동으로 같은 원소는 제외됨)
2. 가로줄 하나에는 암호 코드가 한 세트 이상이 들어있다.
3. 암호 코드 한 세트 (10진수 기준 길이 : 8 / 16진수 기준 길이 : 14의 배수 / 2진수 기준 길이 : 56의 배수)
4. 16진 암호 코드로 된 가로줄 하나를 2진 암호 코드로 변환한다. 
   변환 후 오른쪽에 있는 0은 다 지워도 된다. (어떤 암호던 마지막은 1로 끝나기 때문)
5. 2진 암호 코드를 오른쪽에서 부터 읽어가면서 10진수로 변환한다. 
   10진수 암호 숫자 하나가 차지하는 2진수 암호의 길이는 7의 배수가 된다.
   예) (10진수) 9 = 0001011 = 00000011001111 = 000000000111000111111 ...
   그렇기 때문에 2진수 암호의 전체 길이와 상관없이 0과 1의 비율을 통해 암호의 10진수를 알아낼 수 있다.
   -> 3:1:1:2
6. 2진 코드를 뒤에서부터 읽어나가면서, 1의 개수를 세고(n4), 0의 개수를 세고(n3), 1의 개수를 세면(n2), n1도 알 수 있다. 
   n1 = 7*배수 - (n2 + n3 + n4)
   예) n1:1:1:2 이면 배수는 1이고, n1은 3
   n1:2:2:4 이면 배수는 2이고, n1은 6
   n1:3:3:6 이면 배수는 3이고, n1은 9
   배수는 n2, n3, n4의 최소값임을 알 수 있다.
7. n1, n2, n3, n4를 배수로 나누어 준다. (비율을 알기 위함)
8. 비율을 통해 10진수를 얻을 수 있다.
   0 : (3:2:1:1)
   1 : (2:2:2:1)
   2 : (2:1:2:2)
   ...
   9 : (3:1:1:2)
9. 10진수 8개를 얻으면 암호 코드 한 세트를 얻은 것이다. 암호 코드 한 세트를 얻으면 유효한 암호 코드인지 검사한다. (문제에 유효한 코드의 속성이 주어짐)

*생각지 못한 문제가 하나 있었다.

input 문자열을 받아서 문자열을 for 반복문을 통해 반복할 때, (for i in 문자열) 로 하면 에러가 발생한다.

운영체제 마다 개행문자가 다른데, for i in 문자열 을 실행하면 개행문자를 제대로 인식할 수 없는 것 같다.

그래서 반복문을 for i in range(문자열의 길이) 로 해주니 에러가 해결이 됐다.

코드

import sys
sys.stdin = open('input_1242.txt')


# 코드 부분만 추출하기
def extract_decimal_code(in_str):
    code = list()   # 10진 암호 코드 하나하나씩 저장할 배열 (8개 채우면 빈 배열로 리셋)
    idx = len(in_str) - 1
    # in_str의 뒤->앞으로 역순으로 조사
    while idx >= 0:
        # 1을 만나면 그 때부터 암호코드 추출 시작
        if in_str[idx] == '1':
            # 0001101 이면
            # n1=3 / n2=2 / n3=1 / n4=1
            n1 = n2 = n3 = n4 = 0
            # n4 추출
            while in_str[idx] == '1':
                n4 += 1
                idx -= 1
            # n3 추출
            while in_str[idx] == '0':
                n3 += 1
                idx -= 1
            # n2 추출
            while in_str[idx] == '1':
                n2 += 1
                idx -= 1
            # n1 추출 (n1이 어디까지인지 알 수 없기 때문에
            # 전체 크기인 (7*multiple)에서 n2 n3 n4를 빼면 -> n1
            #   multiple은 배수 (전체 크기가 7, 14, 21, 28 ... 이기 때문)
            multiple = min(n2, n3, n4)
            n1 = (7 * multiple) - (n2 + n3 + n4)
            # 암호 코드 끝나는 부분으로 idx 옮기기
            idx -= n1
            # 배율 빼주기
            #   6 : 4 : 2 : 2 인 경우 -> 3 : 2 : 1 : 1 로 바꿔줌
            n1 //= multiple
            n2 //= multiple
            n3 //= multiple
            n4 //= multiple
            # 3 : 2 : 1 : 1 -> 십진수로 얻기 (원소의 인덱스가 십진수)
            decimal_num = pattern.index((n1, n2, n3, n4))
            # 새로 얻은 십진수를 앞으로 넣는다 (뒤에서 부터 조사했기 때문)
            code.insert(0, decimal_num)
            # 암호 코드 한 세트를 추출했으면 -> 암호 코드 추가해주고, 코드를 담을 변수는 리셋
            if len(code) == 8:
                if ((code[0] + code[2] + code[4] + code[6]) * 3 + code[1] + code[3] + code[5] + code[7]) % 10 == 0:
                    if code not in decimal_codes:
                        decimal_codes.append(code)
                code = list()
        # 암호와 상관없는 부분은 그냥 패스
        else:
            idx -= 1


# 2진수 코드 비율 -> 10진수
pattern = [
    (3, 2, 1, 1), (2, 2, 2, 1), (2, 1, 2, 2), (1, 4, 1, 1), (1, 1, 3, 2),
    (1, 2, 3, 1), (1, 1, 1, 4), (1, 3, 1, 2), (1, 2, 1, 3), (3, 1, 1, 2)
]

# 16진수 -> 2진수
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'
}

T = int(input())
for tc in range(1, T + 1):
    N, M = map(int, input().split())
    in_arr = [input() for _ in range(N)]
    in_arr = list(set(in_arr))  # 중복 row 제거

    decimal_codes = list()
    for i in range(len(in_arr)):
        arr = in_arr[i]
        for j in range(M):
            if arr[j] != '0' or arr[len(arr) - i - 1] != '0':
                # 16진 코드 -> 2진 코드 변환
                binary_code = ''
                for k in range(M):
                    binary_code += hex_to_bin[arr[k]]
                binary_code = binary_code.rstrip('0')
                # 2진 코드 -> 10진수 코드 변환 (유효성 검사, 중복 검사 포함)
                extract_decimal_code(binary_code)
                break
    result = 0
    code_length = len(decimal_codes)
    for i in range(code_length):
        result += sum(decimal_codes[i])

    print('#{} {}'.format(tc, result))