[level 1] [1차] 비밀지도(비트 연산자로 다시 생각해보기)

문제 

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

 

문제 풀이 접근법1

1) 배열의 원소를 10진수에서 2진수로 변환한다. 

2) arr1[i]원소와 arr2[i]원소를 더하여 하나의 배열로 만든다.

3) 새로 만들어진 배열의 원소를 또 다시 각각의 배열로 만든 후, 해당 배열의 원소가 1 이상이면 #으로 변환하고 0이면 공백으로 변환한 뒤 다시 하나의 문자열로 만든다. 

4) 해당 문자열을 반환한다. 

for i in range(len(arr1)):
    arr1[i], arr2[i] = format(arr1[i], 'b'), format(arr2[i], 'b')
    answer.append(int(arr1[i])+int(arr2[i]))
    
for i in range(len(answer)):
    
    s = list(str(answer[i]))
    #print(s)
    
    for j in range(len(s)):
        if s[j] == '0':
            s[j] = " "
        else:
            s[j] = "#"
    
    answer[i]="".join(s)
    
    
        
print(answer)

테스트 2에서 오류가 났다. 

 

해당 풀이에서 잘못된 점은 10진수를 2진수로 변환할 때, n자리수 만큼 나오지도 않는 경우가 있다는 걸 잊고 있었던 거였다. 그렇기 때문에 예를 들어 n이 6일 때, 10진수를 2진수로 변환했을 때의 길이가 5일 경우에는 다른 부분을 0으로 채워줘야 하는데 그렇지 않아서 오류가 발생하는 거였다. 

 

 

문제 풀이 접근법2

위의 풀이에서 n자리수를 채울 수 있도록 부족한 부분은 0으로 채워주었다. 

def solution(n, arr1, arr2):
    answer = []
    s = []
    
    for i in range(len(arr1)):
        arr1[i], arr2[i] = format(arr1[i], 'b'), format(arr2[i], 'b')
        answer.append(str(int(arr1[i])+int(arr2[i])).zfill(n))

    for i in range(len(answer)):
    
        s = list(answer[i])
    
        for j in range(len(s)):
            if s[j] == '0':
                s[j] = " "
            else:
                s[j] = "#"
    
        answer[i]="".join(s)
        
    return answer

 

---

 

다른 분들 풀이

def solution(n, arr1, arr2):
    answer = []
    for i,j in zip(arr1,arr2):
        a12 = str(bin(i|j)[2:])
        a12=a12.rjust(n,'0')
        a12=a12.replace('1','#')
        a12=a12.replace('0',' ')
        answer.append(a12)
    return answer

와 비트 연산?? 진짜 생각도 못함...헐...비트 or연산...진짜 생각도 못함... 

진짜...거짓말 안하고 내 기억 속 어딘가에서 사라진 존재였음(이러면 당연히 안됨...)

 

해당 코드에 나만의 주석을 달아보면 

 

3번째 줄에서 각각 i와 j에 arr1과 arr2의 원소가 차례대로 들어오게 되고

4번째 줄에서 arr1의 i번째 원소와 arr2의 j번째 원소를 bin()함수로 2진수로 바꾼뒤, 동시에 | 연산자를 사용하여서 비트 or 연산을 한다. (이때 슬라이싱으로 앞의 2번째를 빼주는 이유는 bin함수를 사용하면 앞에 ob가 붙기 때문!)

5번째 줄에서 rjust함수로 오른쪽 정렬과 동시에 공백이 있다면 해당 부분을 0으로 대체한다

6~7번째 줄에서는 1이면 #으로, 0이면 공백으로 자리를 변환한다. 

8번째 줄에서 그렇게 변환된 문자열을 answer함수에 추가한다. 

 

진짜...너무 천재적이어서 말이 안나옴 지금...

아닌가 그냥 내가 바보인 것 같기도...아무튼 나중에 다시 풀어봐야겠다!

 

참고: https://hoho325.tistory.com/235

8. 파이썬 비트연산(shift), 논리 연산(and, or, not)

https://lovelydiary.tistory.com/294

파이썬) rjust 함수 사용법 (오른쪽 정렬해서 출력하기)