[SWEA] SWEA 1242 암호코드 스캔 (Python) - Simulation

📌 문제

1. 세로 2000, 가로 500 이하의 크기를 가진 직사각형 배열 안에 16진수로 이루어진 암호 코드 배열이 있다.

 

2. 먼저, 16진수 암호를 모두 2진수로 변환한 뒤, 암호 해독을 해야한다.

 

3. 문제는, 아래와 같이 암호코드의 가로 길이가 늘어난 경우도 존재한다는 것이다.

원래 상태

가로로 늘어난 상태

=> 그래서 각 구간의 "비율"로 접근해야 한다.

 

4. 암호 해독을 마쳤으면, 암호코드의 정상 여부를 확인해야 한다.

• 암호 코드는 숫자 8개로 구성 (7개 고유번호 + 1개 검증코드)
• 암호 코드 검증법 : ((홀수 자리의 합 x 3) + 짝수 자리의 합 + 검증 코드) % 10 == 0

 

5. 정상적인 암호 코드만 찾아서 해당 코드에 포함된 숫자들의 합을 출력한다. 

---

📌 풀이

Code

import sys
input = sys.stdin.readline

# 암호 해독기 (0으로 구성되어 있는 앞부분 제외하고 2, 3, 4번째 부분 개수 비율)
decoder = {'211' : 0, '221' : 1, '122' : 2, '411' : 3, '132' : 4,
           '231' : 5, '114' : 6, '312' : 7, '213' : 8, '112' : 9}

# 16개의 숫자에 대한 2진수 표현
hex_dict = {
    '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'
}

for tc in range(1, 1+int(input())):
    H, W = map(int, input().split())                        # H: 배열 세로, W: 배열 가로
    arr = list(set([input().strip() for _ in range(H)]))    # set으로 중복되는 행은 지우기
    arr = sorted(arr)[1:]                                   # 0만 있는 행은 제거
    answer = 0                                              # 올바른 검증코드의 각 숫자 합을 모두 더할 변수    
    code_history = []                                       # 지금까지 나왔던 암호 코드 넣을 리스트
    
    for row in arr:
        # 16진법으로 표현된 행을 2진법으로 바꾸기
        hex_row = ''
        for h in row:
            hex_row += hex_dict[h]
        # 왼쪽 0 다 지우기
        hex_row = hex_row.lstrip('0')

        cnt = 0                                 # 암호 자릿수 카운트
        part1 = part2 = part3 = 0               # part 1~3 사이즈 저장
        even = odd = 0                          # 홀수, 짝수 합 저장
        code = ''
        for ch in hex_row:                      # 이번 행에 있는 숫자들 쭉 순회
            # part 1,2,3 크기 채우기
            if ch == '1' and part2 == 0:
                part1 += 1
            elif ch == '0' and part1 > 0 and part3 == 0:
                part2 += 1
            elif ch == '1' and part2 > 0:
                part3 += 1
            # part 1,2,3 크기 다 채웠으면
            elif part3 > 0:
                cnt += 1                                    # 암호 한자리 들어옴
                # 무조건 part 1,2,3 비율 중에 1이 있기 때문에 최소값이 비율 1일 것임 (전체를 그걸로 나눠주면 됨)
                multiply = min(part1, part2, part3)         # 가로 크기 몇 배 늘어났는지
                # 늘어난 배수만큼 나눠주기
                ratio = map(lambda x: x//multiply, [part1, part2, part3])    
                key = ''.join(list(map(str, ratio)))        # 숫자였으니 문자로 바꾸고 합치기
                num = decoder[key]                          # 해독된 숫자
                code += str(num)                            # 해독된 숫자 하나씩 추가
                
                # 암호 길이가 8에 도달했고, 앞서 나왔던 암호가 아니면
                if len(code) == 8:
                    if (odd*3 + even + num) % 10 == 0 and code not in code_history:
                        answer += odd + even + num
                        code_history.append(code)
                    even = odd = cnt = 0                    # 홀수, 짝수 합 초기화
                    code = ''                               # 암호 코드 초기화
                # 암호 길이가 8에 도달하지 못했으면
                else:
                    if cnt % 2 == 1:                        # 홀수 합 모아주기
                        odd += num
                    else:                                   # 짝수 합 모아주기
                        even += num
                                
                part1 = part2 = part3 = 0                   # part 1~3 사이즈 초기화

    print(f'#{tc}', answer)

---

Solution

1. 암호 해독기, 16 → 2진수 변환기 딕셔너리 정의

• 암호 해독기: 실제로는 총 4개의 구간이지만, 가장 앞에 있는 구간은 0으로만 이루어져 있기 때문에, 뒤에 있는 3개의 구간 크기 비율만 고려 ('211'란 2:1:1 비율을 의미)

# 암호 해독기 (0으로 구성되어 있는 앞부분 제외하고 2, 3, 4번째 부분 개수 비율)
decoder = {'211' : 0, '221' : 1, '122' : 2, '411' : 3, '132' : 4,
           '231' : 5, '114' : 6, '312' : 7, '213' : 8, '112' : 9}

• 16 → 2진수 변환기: 16진수를 2진수로 변환하기 위해, 각 16진수에 대응하는 2진수를 딕셔너리에 key-value 쌍으로 넣기

# 16개의 숫자에 대한 2진수 표현
hex_dict = {
    '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'
}

 
2. set 자료구조를 사용하여 중복되는 행은 사전에 제거하고, 남은 행 중에 0으로만 채워져 있는 행도 제거

arr = list(set([input().strip() for _ in range(H)]))    # set으로 중복되는 행은 지우기
arr = sorted(arr)[1:]                                   # 0만 있는 행은 제거

 
3. 각 행을 순회하기

for row in arr:

4. 16진법으로 표현된 행을 2진법으로 바꾸고, 왼쪽의 0은 다 지우기

# 16진법으로 표현된 행을 2진법으로 바꾸기
hex_row = ''
for h in row:
    hex_row += hex_dict[h]
# 왼쪽 0 다 지우기
hex_row = hex_row.lstrip('0')

 

5. 비율을 측정할 3개의 구간 크기 측정하기

• part2가 아직 0인 상태에서, '1'이 들어오면, part1 크기 1 증가

• part1이 0보다 크고, part3이 0이면서, '0'이 들어오면 part2 크기 1 증가

• part2가 0보다 큰 상태에서, '1'이 들어오면 part3 크기 1 증가

• part3이 0보다 큰 상태에서, '0'이 들어오면 3개의 구간 사이즈를 다 구했다는 것

=> 끝에는 무조건 0일 수 밖에 없는게, 다음 문자의 시작은 무조건 0부터고, 마지막 문자라 하더라도 암호가 0으로 패딩되어 있기 때문

6. 비율을 측정하기 위해 가장 작은 사이즈인 part의 크기를 각 part에 나눠주기

암호 패턴을 보면, 비율에는 반드시 1이 포함되어 있습니다.
즉, 비율이 1인 사이즈가 단위 기준이 되는 것이죠.

 

# 무조건 part 1,2,3 비율 중에 1이 있기 때문에 최소값이 비율 1일 것임 (전체를 그걸로 나눠주면 됨)
multiply = min(part1, part2, part3)         # 가로 크기 몇 배 늘어났는지
# 늘어난 배수만큼 나눠주기
ratio = map(lambda x: x//multiply, [part1, part2, part3])​

 

7. 비율을 구했으니, 해독기의 key 형식에 맞춰서 해독기에 넣고 해독한 뒤, 해독된 숫자를 code 변수에 차곡 차곡 저장하기 (반복을 통해 해독된 숫자가 code 변수에 쌓이게 됨)

key = ''.join(list(map(str, ratio)))        # 숫자였으니 문자로 바꾸고 합치기
num = decoder[key]                          # 해독된 숫자
code += str(num)                            # 해독된 숫자 하나씩 추가

 

8. 암호 길이가 8에 도달할 때까지, 홀수번째 수와 짝수번째 수를 각각 홀수 합, 짝수 합 변수에 모아주기 (누적 합)

 

9. 암호 길이가 8에 도달하면, 암호 코드 검증 식에 맞춰 검증하고, code_history 리스트 변수에 저장

• code_history 변수는, 같은 암호 코드가 나올 경우 암호 코드 검증 연산을 하지 않도록 하기 위해 만든 변수

10. 올바른 암호코드에 대해서만 해당 코드에 포함된 숫자들의 합을 구해 answer 변수에 더하기

 

11. answer 출력

---

깨달은 점

지독한 구현 문제였습니다..

 

코딩을 시작하기 전에 로직 설계를 꼼꼼히 하는 것이 얼마나 중요한지 깨닫게 하는 문제였네요.

(쓸데없는 삽질하느라 9시간 정도 사용한 것 같아요..)

 

반복되는 행을 제거하지 않아 필요없는 반복을 수행하기도 하고,

input().strip()과 같은 디테일을 챙기지 못해서 한참을 헤메기도 했습니다.

 

앞으로는 이렇게까지 삽질하고 싶지 않아요ㅠㅠ