[SWEA-파이썬] 1242: 암호코드 스캔

즐거운 PS 👩‍💻🥰

[SWEA-파이썬] 1242: 암호코드 스캔

dalin❤️ 2021. 10. 7. 20:16

ㅠㅠㅠㅠㅠㅠ
3~4시간 힘겨운 시간을 보내고 ㅠㅠㅠ 드디어 맞았다 ㅠㅠㅠㅠㅠ
이렇게 오래 씨름한 문제는 오랜만이다...
접근은 그렇게 어렵지는 않았고, 1시간 만에 파이참에서는 정답이 나오게 코드를 짤 수 있었다.
그런데 문제 채점 사이트에서 런타임 에러 나와서 해결하느라고 정말 정말 힘들었다 ..!!

맨 처음 짠 코드 👩‍💻

import sys

sys.stdin = open('1242_input.txt')
T = int(input())
hex_change = {
    '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',

}

secret_code = {
    '0001101': 0,
    '0011001': 1,
    '0010011': 2,
    '0111101': 3,
    '0100011': 4,
    '0110001': 5,
    '0101111': 6,
    '0111011': 7,
    '0110111': 8,
    '0001011': 9}


def find_start():
    # 위 -> 아래, 오-> 왼 보면서 암호 코드의 시작 지점을 찾는다.
    start_candidates = []
    for i in range(1, N - 1):
        for j in range(M * 4 - 1, 56, -1):
            if arr[i][j] != '0':
                # 암호코드(시작 지점)인지 보기
                # if arr[i][j + 1] == '0' and arr[i - 1][j] == '0':  # 처음에 등장할 때만 볼 것
                if arr[i - 1][j] == '0':  # 처음에 등장할 때만 볼 것
                    start_candidates.append((i, j))
    return start_candidates


def change_to_hex(num):
    final = ''
    for i in range(len(num)):
        final = final + hex_change[num[i]]
    return final


def change_ratio(binary_num, ratio):
    final = ''
    for k in range(0, 56 * ratio, ratio):
        # 그만큼 배로 했으면, 줄일 수 있어야 함.
        num = binary_num[k]
        for kk in range(k + 1, k + ratio):
            if num != binary_num[kk]:
                return False
        final = final + binary_num[k]
    return final


for tc in range(1, T + 1):

    N, M = map(int, input().split())
    arr = list(list(change_to_hex(input())) for _ in range(N))
    # arr = list(list(change_to_hex(input())) for _ in range(N))
    # 처음부터 16진수 -> 2진수

    secret_code_total = 0  # 정상적인 암호코드들에 포함된 숫자들의 합

    # 거꾸로 보다가 위 값이 0인지 확인 -> 시작점 후보로 넣기
    start_idx_candidates = find_start()

    for start_idx_candidate in start_idx_candidates:

        i = 0
        while start_idx_candidate[1] - 56 - 56 * i >= 0:  # 비율로 계산해야 함. 7 -> 14 -> 21 쭉 보기
            secret_code_candidate = ''.join(
                arr[start_idx_candidate[0]][start_idx_candidate[1] - 55 - 56 * i:start_idx_candidate[1] + 1])
            i += 1

            # 비율에 맞게 줄임
            tiny_binary_secret_code_candidate = change_ratio(secret_code_candidate, i)
            if tiny_binary_secret_code_candidate == False:
                continue

            else:
                # 암호 코드로 변환
                secret_code_s = []
                for k in range(0, 50, 7):
                    if secret_code.get(tiny_binary_secret_code_candidate[k:k + 7]) != None:
                        secret_code_s.append(secret_code.get(tiny_binary_secret_code_candidate[k:k + 7]))
                    else:
                        break
                # 검증 코드 확인하여 정상적인 암호 코드인지 확인
                if len(secret_code_s) == 8:
                    verification_code = (secret_code_s[0] + secret_code_s[2] + secret_code_s[4] + secret_code_s[6]) * 3 + (secret_code_s[1] + secret_code_s[3] + secret_code_s[5]) + secret_code_s[7]

                    if verification_code % 10 == 0:
                    # 암호 코드 수 더하기
                        secret_code_total += sum(secret_code_s)
    print(f'#{tc} {secret_code_total}')

파이참에서는 20개 테스트 케이스 모두 정답으로 나왔다.
그런데 채점 사이트에서는 처음부터 런타임 에러가 나왔다.

런타임 에러가 나왔던 이유 🤔

1. input받을 때 `strip()`을 꼭 해줘야 했다.

(이건 SWEA 이 문제 질문 & 답변 란에서 본 것이다.)
-> 하지만 나는 이걸 해도 계속 16번까지만 맞고, 나머지는 런타임 에러가 나왔다. (파이참에서는 정답인데, 채점 사이트에서 그랬다.)

그리고 다시 고민...

나는 '시간 초과가 나도 런타임 에러라고 하나..? 시간 초과는 시간 초과라고 알려줄 것 같은데..?' 라고 생각했다. (시간 초과는 시간 초과라고 알려준다..! 그때는 왠지 모르게 이렇게 생각했다.. ) 그러면서 시간을 최대한 줄이기 위해서 노력했다. 여러 가지를 조금씩 고쳤지만 가장 많이 고친 건 find_start() 부분이다.

def find_start():
    # 위 -> 아래, 오-> 왼 보면서 암호 코드의 시작 지점을 찾는다.
    start_candidates = []
    for i in range(1, N - 1):
        j = M * 4 - 1
        while j >= 56:
            if arr[i][j] == '1':
                # 암호코드(시작 지점)인지 보기
                if arr[i - 1][j] == '0' and arr[i][j + 1] == '0':  # 처음에 등장할 때만 볼 것
                    start_candidates.append((i, j))
                j -= 7
            else:
                j -= 1
    return start_candidates

전에는 j가 M*4-1부터 56까지 인덱스 1씩 줄여가면서 모두 보았다. 또한 1이 나오고, 그 위가 0이면 모두 시작 지점 후보(start_candidates)에 넣었다.
이번에는 j가 M*4-1부터 56까지 보긴 보되, 안 봐도 되는 부분은 안 보게 했다. 1이 나왔으면 j를 7씩 줄인 것이다. (암호 코드는 최소 7개씩으로 이루어졌기 때문)
또한 1이 나오고 그 위가 0이고, 그 오른쪽도 0일 때 시작 지점 후보에 넣었다.

이렇게 바꾸었더니 파이참에서의 실행 시간은 많이 줄어들었다. 하지만 채점 사이트에서는 여전히 런타임 에러였다..ㅠㅠ

2. 메모리 초과

그 이유는 메모리 초과 때문인 것 같다.
나는 처음에 입력받은 16진수를 2진수로 바꿔서 쭉 ~~ 2차원 리스트에 저장했다. arr = list(list(change_to_hex(input())) for _ in range(N))
그러면 이 2차원 리스트는 최대 2000개 원소가 있는 리스트 2000개가 된다. (세로는 최대 2000개이고, 가로는 최대 500개인데 16진수를 2진수로 바꾸니 4배로 늘어나서 2000개가 된다.)
'시간은 줄여봤는데도 런타임 에러네ㅠㅠ 시간 초과는 시간 초과라고 하지 런타임 에러는 아닌 것 같다.' 라는 생각이 들었다. 다른 문제는 없는 것 같아서 고민하다가 '리스트로 하면 너무 메모리를 많이 차지하려나? 문자열로 받아도 되니까 그렇게 해야지'하는 생각이 들었다.
그래서 arr = list(change_to_hex(input().strip()) for _ in range(N)) 이렇게 바꾸니까 맞았다.

나중 코드 👩‍💻

hex_change = {
    '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',

}

secret_code = {
    '0001101': 0,
    '0011001': 1,
    '0010011': 2,
    '0111101': 3,
    '0100011': 4,
    '0110001': 5,
    '0101111': 6,
    '0111011': 7,
    '0110111': 8,
    '0001011': 9}


def change_to_hex(num):
    final = ''
    for ii in range(len(num)):
        final = final + hex_change[num[ii]]
    return final


def find_start():
    # 위 -> 아래, 오-> 왼 보면서 암호 코드의 시작 지점을 찾는다.
    start_candidates = []
    for i in range(1, N - 1):
        j = M * 4 - 1
        while j >= 56:
            if arr[i][j] == '1':
                # 암호코드(시작 지점)인지 보기
                if arr[i - 1][j] == '0' and arr[i][j + 1] == '0':  # 처음에 등장할 때만 볼 것
                    start_candidates.append((i, j))
                j -= 7
            else:
                j -= 1
    return start_candidates


def change_ratio(binary_num, ratio):
    final = ''
    if ratio == 1:
        return binary_num
    for k in range(0, 56 * ratio, ratio):
        # 그만큼 배로 했으면, 줄일 수 있어야 함.
        num = binary_num[k]
        for kk in range(k + 1, k + ratio):
            if num != binary_num[kk]:
                return False
        final = final + binary_num[k]
    return final

T = int(input().strip())
for tc in range(1, T + 1):

    N, M = map(int, input().strip().split())
    arr = list(change_to_hex(input().strip()) for _ in range(N))
    # 처음부터 16진수 -> 2진수

    secret_code_total = 0  # 정상적인 암호코드들에 포함된 숫자들의 합

    # 거꾸로 보다가 위 값이 0인지 확인 -> 시작점 후보로 넣기
    start_idx_candidates = find_start()

    for start_idx_candidate in start_idx_candidates:
        i = 0
        while start_idx_candidate[1] - 55 - 56 * i >= 0:  # 비율로 계산해야 함. 7 -> 14 -> 21 쭉 보기
            secret_code_candidate = ''.join(
                arr[start_idx_candidate[0]][start_idx_candidate[1] - 55 - 56 * i:start_idx_candidate[1] + 1])
            i += 1

            # 비율에 맞게 줄임
            tiny_binary_secret_code_candidate = change_ratio(secret_code_candidate, i)
            if tiny_binary_secret_code_candidate == False:
                continue

            else:
                # 암호 코드로 변환
                secret_code_s = []
                for k in range(0, 50, 7):
                    if secret_code.get(tiny_binary_secret_code_candidate[k:k + 7]) == None:
                        break
                    else:
                        secret_code_s.append(secret_code.get(tiny_binary_secret_code_candidate[k:k + 7]))
                # 검증 코드 확인하여 정상적인 암호 코드인지 확인
                if len(secret_code_s) == 8:
                    verification_code = (secret_code_s[0] + secret_code_s[2] + secret_code_s[4] + secret_code_s[
                        6]) * 3 + (secret_code_s[1] + secret_code_s[3] + secret_code_s[5]) + secret_code_s[7]

                    if verification_code % 10 == 0:
                        # 암호 코드 수 더하기
                        secret_code_total += sum(secret_code_s)

    print(f'#{tc} {secret_code_total}')

결과, 소감 😀

처음 코드에서 input().split() 을 수정하니 16문제 pass, 17번부터 런타임 에러가 나왔다.
find_start() 를 고쳐서 시간을 단축했지만 계속 런타임 에러였다.
arr = list(change_to_hex(input().strip()) for _ in range(N))을 수정하니 드디어 맞았다 !! (5,412 ms)

PASS한 후에, '혹시나..?' 하는 마음에 처음 코드에서 input().split() , arr = list(change_to_hex(input().strip()) for _ in range(N))만 수정해봤는데도 맞았다. 실행 시간은 21,497 ms가 나왔다.

결국은 PASS하고 왜 런타임 에러였는지 알아서 뿌듯하다!!

요즘에 문제 풀 때 시간 복잡도는 약간이나마 확인하려고 하는데, 공간 복잡도는 전혀 생각하지 않았던 것을 반성했다..ㅠㅠ 공간 복잡도 계산하는 것은 잘 모르는데 공부해야겠다. 런타임 에러가 나오는 이유도 더 공부해야겠다.

728x90

'즐거운 PS 👩‍💻🥰' 카테고리의 다른 글

[백준-파이썬] 20440: 니가 싫어 2 (0)	2021.10.07
[백준-파이썬] 1323: 숫자 연결하기 (0)	2021.10.07
[백준-파이썬] 10971: 외판원 순회 2 (0)	2021.10.07
[백준-파이썬] 17394: 핑거 스냅 (0)	2021.10.07
[백준-파이썬] 14395: 4연산 (0)	2021.10.07

현재글[SWEA-파이썬] 1242: 암호코드 스캔

(전) 주니어 프론트엔드 개발자의 아카이브 👩‍💻

BFS, 생각, 백준, 독서, dfs, 일기, 회고, 파이썬, DP, 책, 정렬, 브루트포스, 구현, 개발, 아티클, SWEA, 싸피, CSS, 우선순위큐, 그리디,

Today :
Yesterday :

Dalin's Archive