[SWEA][D4][#04366] 정식이의 은행업무

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

삼성은행의 신입사원 정식이는 실수를 저질렀다.

은행 업무가 마감되기 직전인 지금, 송금할 금액을 까먹고 말았다.

하지만 다행스럽게도 정식이는 평소 금액을 2진수와 3진수의 두 가지 형태로 기억하고 다니며, 기억이 명확하지 않은 지금조차 2진수와 3진수 각각의 수에서 단 한 자리만을 잘못 기억하고 있다는 것만은 알고 있다.

예를 들어 현재 기억이 2진수 1010과 3진수 212을 말해주고 있다면 이는 14의 2진수인 1110와 14의 3진수인 112를 잘못 기억한 것이라고 추측할 수 있다.

정식이는 실수를 바로잡기 위해 당신에게 부탁을 하였다.

정식이가 송금액을 추측하는 프로그램을 만들어주자.

( 단, 2진수와 3진수의 값은 무조건 1자리씩 틀리다. 추측할 수 없는 경우는 주어지지 않는다. )

입력

10개 이하의 테스트 케이스가 주어진다.

첫 번째 줄에는 테스트케이스의 개수가 주어진다.

하나의 케이스는 두 줄로 되어있다.

각 케이스의 첫 번째 줄은 정식이가 기억하는 송금액의 2진수 표현, 두 번째 줄은 송금액의 3진수 표현이 주어진다.

(3 ≤ 2진수, 3진수의 자릿수 <40)

출력

원래 송금하기로 하였던 금액을 케이스마다 한 줄에 하나씩 출력한다.

예제

입력

1
1010
212

출력

#1 14

My Sol

def dfs():
    global arr2, L2
    for p2 in range(1, L2):
        arr2[p2] = di2[arr2[p2]]
        val2 = 0
        for i in range(L2):
            val2 += arr2[i] * 2**(L2-1-i)

        if check3(val2):
            return val2
        arr2[p2] = di2[arr2[p2]]
    return 0


def check3(val2):
    global arr3, L3
    for p3 in range(L3):
        ov = arr3[p3]
        for sv in di3[ov]:
            arr3[p3] = sv

            val3 = 0
            for i in range(L3):
                val3 += arr3[i] * 3**(L3-1-i)

            if val3 == val2:
                return val2
        arr3[p3] = ov
    return 0


di2 = {0:1, 1:0}
di3 = {0:[1, 2], 1:[0, 2], 2:[0, 1]}
T = int(input())
for tc in range(1, T+1):
    arr2 = list(map(int, (list(input()))))
    arr3 = list(map(int, (list(input()))))
    L2, L3 = len(arr2), len(arr3)
    print(f'#{tc} {dfs()}')

한 자리씩 다르기 때문에 2진수의 자리마다 하나씩 switch한 값과 3진수의 자리마다 가용한 다른 두 개의 수를 바꿔가며 해당 수가 2진수를 바꾼 값과 같은지를 체크하면 되겠다. 값을 바꾸는 것은 모두 dictionary를 사용하여 효율적으로 조회할 수 있도록 하였다. 2진수의 값을 바꾸는 로직은 dfs() 함수에서 정의하였고, 값을 바꾼 리스트를 10진수형으로 바꾸어 check3() 함수 내에 전달해준다.

check3() 함수는 마찬가지로 3진수의 첫 자리부터 끝 자리까지 하나씩 dictionary의 key로 사용하여 가용한 나머지 2개의 수를 리스트로 받아오는데, 이를 각각 arr3의 해당 자리에 바꿔 넣고 이 arr3로 val3, 즉 3진수를 10진수로 바꾸는 로직을 통해 값을 도출한다. 이 각각의 값과 val2를 비교하다가, 맞는 순간이 나오면 이때의 val2(혹은 val3)를 반환한다.

만약 2진수의 이번 자릿수를 바꾼 것이 3진수를 어떻게 조작하더라도 같은 값이 나오지 않는다면 check3() 함수는 0을 반환하기 때문에 dfs() 함수 내에서는 다음 2진수의 자리를 확인하며 진행할 수 있다.

결과

PASS