Level 1 [1차] 비밀지도 <KAKAO 2018 BLIND RECRUITMENT> Python3

programmers.co.kr/learn/courses/30/lessons/17681?language=python3

코딩테스트 연습 - [1차] 비밀지도

 

최종 풀이

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

def solution(n, arr1, arr2):
    answer = []
    for i in range(n):
        answer.append(bin(arr1[i]|arr2[i])[2:].zfill(n).replace('1', '#').replace('0', ' '))
    return answer

---

풀이 과정

풀이 시간 12분

 

def solution(n, arr1, arr2):
    answer = []
    for i in range(n):
        answer.append(bin(arr1[i]|arr2[i])[2:].zfill(n).replace('1', '#').replace('0', ' '))
    return answer
#시간복잡도 = O(n^4 log n), 공간복잡도 = O(n^2)

1. bin(arr1[i] | arr2[i])[2:] => arr1[i]과 arr2[i]를 OR 연산한 결과를 2진수로 표현하기 -> O(log n)

두 정수를 OR 연산하면 두 정수를 2진수로 표현했을 때 OR 연산을 한 이후의 정수 값을 반환한다.

OR 연산한 정수 결과 값을 파이썬 내장함수인 bin()을 사용하여 2진수로 변환한 문자열로 출력한다.

bin()함수를 통해 O(log n)의 시간복잡도로 정수를 이진수로 표현한 문자열로 변환할 수 있다. 이때 앞에 접두어 '0x'가 붙는다.

따라서 인덱스 2부터 출력하도록 문자열을 자른다.

 

2. zfill(n) => 앞에 '0'을 채워 n자리로 표현하기 -> O(n)

파이썬 문자열 내장함수인 zfill(n)은 문자열 길이를 n으로 만들기 위해 앞에 '0'을 채워준다. 시간복잡도는 만일 1.의 결과의 문자열 길이가 1인 경우 n-1개의 '0'을 앞에 채워줘야 하므로 O(n)이 소요된다.

 

3. replace('1', '#').replace('0', ' ') => 벽은 '#'로, 공백은 ' '로 바꿔주기 -> O(n^2)

 

위 1 ~ 3.과정을 n번 반복하기 때문에 시간복잡도는 O(n^4 log n)으로 생각된다.

문제의 제한사항을 보면 n이 16이하라고 되어있으니 최악의 경우 2^16 × log(16) = 78913.2071833이므로, 78914번의 연산이 이뤄질 것으로 예상할 수 있다.

공간복잡도는 answer 리스트의 크기가 n x n이므로 O(n^2)이다.

---

이전 풀이

풀이 시간  24분

 

def solution(n, arr1, arr2):
    answer = []
    for a1, a2 in zip(arr1, arr2):  
        answer.append(bin(a1 | a2)[2:].rjust(n, "0").replace("1", "#").replace("0"," "))
    return answer

풀이 과정에 앞서!

 나는 프로그래머스의 모든 문제를 Level 1부터 풀어왔었다. 현 시점으로 Level 2까지 문제 풀이를 마친 후에 2018 KAKAO BLIND RECRUITMENT [1차] 코딩테스트를 5시간동안 혼자 진행해봤다. 문제는 다음과 같이 구성되어 있다.

1. 비밀지도 <Level 1>
2. 다트게임 <Level 1>
3. 캐시 <Level 2>
4. 셔틀 버스 <Level 3>
5. 뉴스 클러스트링 <Level 2>
6. 프랜즈 4블록 <Level 2>
7. 추석트래픽 <Level 3>

 여기서 이전에 풀어본 문제는 <Level 1>인 비밀지도와 다트게임이었고 나머지 문제들은 이번에 처음 풀어보았다. 나는 5시간 동안 총 5문제를 풀었다.(참고로, 카카오 테크 블로그에 가보니 당시 4개를 풀면 합격이라고 나와있었다.)

비밀지도와 다트게임을 이전에 풀어봤지만 너무 오래돼서 문제도 까먹었었다. 하지만 로그에 남았던 이전 코드를 따로 기록해뒀고, 그 코드는 아래에 적어두었다. 코드를 비교해보면 확실히 <Level 1>을 풀었을 때보다는 지금 훨씬 더 발전했다는 게 눈으로 보여서 기뻤다...

나머지 2-7번 문제들도 이 블로그에 포스팅되어 있으니 아래 참고 부분을 확인하면 좋겠다.

 

 그렇다면, 이제 1번 비밀지도에 대한 풀이 과정을 적어보도록 하겠다.

 

1. OR 비트 연산 하기

 먼저, 정수 배열로 암호화 되어 있는 두 지도를 2진수로 바꾸어 겹쳐서 암호를 해독할 수 있다고 했다. 어느 한 쪽이 1이면 벽을 나타내고 둘 다 0이면 공백을 의미한다고 했다. 나는 이를 통해 바로 OR 비트 연산을 생각해냈다. 입력으로 들어오는 arr1과 arr2의 각 자리 수들을 각각 OR 비트 연산 하면 정수를 2비트 수로 바꾸고, 둘 중 하나라도 1이 있다면 1을, 둘 다 0인 경우 0을 반환하여 나온 2 비트 수의 연산 결과를 10진수로 반환해준다. 즉, a = 5, b = 4라고 한다면 a | b = 101(2) | 10(2) = 111(2) = 7이 반환된다.

이렇게 OR 비트 연산을 한 결과를 2진수로 바꿔준다면, 두 지도를 겹쳐서 어디에 벽이 있고 어디에 공백이 있는지를 알 수 있다.

이를 코드로 나타내면 다음과 같다.

    for a1, a2 in zip(arr1, arr2):  
        bin(a1 | a2)[2:]

bin() 함수는 10진수를 2진수로 바꿔주는 문자열 내장 함수로 결과는 앞에 '0x'가 붙은 문자열 형태로 반환한다. 따라서 a1 | a2한 결과를 이진수로 바꿔주고 앞에 '0x'를 슬라이스 해주면 a1과 a2의 비트 연산 결과를 2진수로 표현한 값이 발생한다. for문과 zip을 활용해 arr1과 arr2의 각각의 요소들을 a1과 a2로 불러와 비트 연산을 해주는 것이다.

 

2. n 자리 수 맞추기

 만약, a1 = 5, a2 = 4이고 n = 5라고 해보자. 그러면 위의 OR 비트 연산을 한 결과 111이 반환되는데, n 자리 수 만큼 맞춰줘야 한다. 따라서 앞에 2개의 0을 붙여줘야 한다. 이는 rjust() 문자열 내장 함수를 통해 구현할 수 있다. rjust(n, '0')을 하면 n 자리 수에 맞춰 앞에 빈 부분을 '0'으로 채워준다. 1.과 2의 과정을 합친 코드는 다음과 같다.

    for a1, a2 in zip(arr1, arr2):  
        bin(a1 | a2)[2:].rjust(n, "0")

 

 

3. '1' -> '#'와 '0' -> ' '로 바꾸기

 이제, 마지막으로 출력을 위해 '1'은 벽을 나타내는 '#'으로, '0'은 공백인 ' '로 바꿔주자. 이 또한 문자열 내장 함수인 replace()를 통해 구현할 수 있다.

그 결과 최종 코드는 다음과 같다.

def solution(n, arr1, arr2):
    answer = []
    for a1, a2 in zip(arr1, arr2):  
        answer.append(bin(a1 | a2)[2:].rjust(n, "0").replace("1", "#").replace("0"," "))
    return answer

이렇게 1. 2. 3. 과정을 모두 거쳐 만들어진 문자열을 리스트 answer에 append 해주면 정답이다.

 

 [1차] 비밀지도는 이렇게 문자열 내장 함수를 적절히 사용해서 짧은 코드로 구현할 수 있었던 것이 포인트인 것같다. 과정에서 나온 문자열 내장 함수와 그 다음 문제들을 참고하고 싶은 분은 아래 참고를 보면 된다.

 

 

---

# 이전에 작성한 코드

 이 코드가 내가 처음으로 비밀지도를 풀었던 코드이다. 다시 리뷰해보니 그땐 파이썬을 접한지 얼마 안됐기 때문에 문자열 내장 함수들을 잘 몰라서 10진수를 2진수로 바꾸는 코드도 직접 작성했었고, 그렇게 바꾼 2진수로 표현한 각 자리 수를 더해주면서 1 이상이면 '#'으로, 아니면 ' '으로 표현한 것 같다. 이렇게 시간이 지나 현재 내가 작성한 코드와 이전에 작성했던 코드를 다시 보니 감회가 새롭고 열심히 공부해야 겠다는 자극이 된다. 파이썬은 내장 함수와 라이브러리가 다양해서 문제를 많이 풀어보면서 익히는 게 중요하다는 것을 새삼 깨달았다. Level 1까지 풀고 난 뒤와 Level 2까지 풀고 난 뒤에 스스로 성장했다는게 느껴져서 뿌듯하다. 벌써부터 Level 3까지 문제를 푼 뒤에는 얼마나 성장했을지 기대된다. 그래서 결론은 성실히 공부하면 된다!! 더 열심히 하자 화이팅!!!

import numpy as np
def solution(n, arr1, arr2):
    answer = []
    pass1 = []
    pass2 = []
    for i in range(n):
        num1=[]
        num2=[]
        pass1.append([])
        pass2.append([])
        for j in range(n):
            pass1[i].append(arr1[i]%2)
            arr1[i]=arr1[i]//2
            pass2[i].append(arr2[i]%2)
            arr2[i]=arr2[i]//2
        pass1[i].reverse()
        pass2[i].reverse()
    pass3 = np.array(pass1) + np.array(pass2)
    for i in range(n):
        s_ans=''
        for j in range(n):
            if(pass3[i][j]>0):
                s_ans+='#'
            else:
                s_ans+=' '
        answer.append(s_ans)
        
    return answer

---

참고

• 2. 다트게임 2021/02/09 - [코테 노트/프로그래머스] - Level 1 [1차] 다트게임 Python3

Level 1 [1차] 다트게임 Python3

• 3. 캐시 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 캐시

Level 2 [1차] 캐시

• 4. 셔틀버스 https://hwayomingdlog.tistory.com/105

Level 3 [1차] 셔틀버스 Python3

• 5. 뉴스 클러스터링 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 뉴스 클러스터링

Level 2 [1차] 뉴스 클러스터링

• 6. 프랜즈 4블록 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 프랜즈 4블록

Level 2 [1차] 프랜즈 4블록

• 7. 추석트래픽 https://hwayomingdlog.tistory.com/106

Level 3 [1차] 추석 트래픽 Python3

---

• 2021/01/21 - [Python/내장 함수] - bin, oct, hex

bin, oct, hex

• 2021/02/09 - [Python/내장 함수] - replace, rjust

replace, rjust