[KAKA0] 2020 KAKAO BLIND RERUITMENT

2020 카카오 블라인드 코딩테스트

 

 

카카오 공식해설

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

 

 

 

 

문제1) 문자열 압축(정답률: 25.9%)

 

풀이방식

문자열을 모든 경우의 수로 분할 후 가장 짧은 방법을 선택

 

 

1. 1~N번까지 모든 경우의 수로 분할

 

2.  i번 분할할 때마다:

•    처음값을 변수(num)로 저장하고 다음 문자열과 비교
•    값이 일치하면 cnt값을 1증가 시켜주고
•    일치하지 않을경우, cnt값이 2이상이라면 cnt+num을 붙여주고 cnt값이 2미만이라면 num만 붙여줌
•    마지막 절차로 마지막 연산을 더해줌
•    최솟값(result)을 answer과 비교하여 갱신

 

 

 

소스코드

 

# 문자열 압축 

def solution(s):
    result = 1e9
    
    def divide(list, n):
        arr = []
        for i in range(0, len(list), n):
            arr.append(list[i:i+n])
        return arr
    
    for step in range(1, len(s) // 2 + 2):
        cnt = 1
        answer = ''
        arr = divide(s, step)
        num = arr[0]
        for i in range(1, len(arr)):
            if num == arr[i]:
                cnt += 1
            else:
                if cnt >= 2:  
                    a = str(cnt) + str(num)
                    answer += a
                    cnt = 1
                    num = arr[i] 
                else:   
                    answer += num
                    cnt = 1
                    num = arr[i] 
        answer += str(cnt) + num if cnt >= 2 else num
        result = min(result, len(answer))
        answer = ''
    
    return result

 

 

// 가장 쉬운 1번문제라는데 정답률이....

   나도 꽤 헷갈리고 시간이 오래걸렸다.ㅋㅋㅋ

 

 

 

문제2) 괄호변환(정답률: 23.1%)

 

풀이방식

재귀함수를 사용해서 주어진 로직대로 구현

 

 

1. 균형잡힌 괄호 문자열로 분할하는 함수 작성

• '('와 ')'의 개수를 비교하여 개수가 같으면 분할된 배열을 반환

 

2. 올바른 괄호 문자열 판별하는 함수 작성

• '('와 ')'의 개수를 비교하여 '('의 개수가 더 적을시 False 반환
• 반복문이 끝났을떄 '('와 ')'의 개수가 같으면 True 반환

 

2.  solution 로직 구현:

이것과 그대로 소스코드로 옮기면 됨

solution 함수 부분

 

 

소스코드

def solution(p):
    answer = ''
    if p == '':
        return answer
    
    u, v = balanced(p)
    # '올바른 괄호 문자열'이면 v에 대해 함수를 수행한 결과를 붙여 반환
    if correct(u):
        answer = u + solution(v)
    
    else:
        answer = '('
        answer += solution(v)
        answer += ')'
        u = list(u[1:-1])
        for i in range(len(u)):
            if u[i] == '(':
                u[i] = ')'
            else:
                u[i] = '('
        answer += "".join(u)
    return answer


# 균형잡힌 괄호 문자열 분할
def balanced(arr):
    left = 0
    right = 0
    for idx, data in enumerate(arr):
        if data == '(':
            left += 1
        else: right += 1
        if left == right:
            return arr[:idx+1], arr[idx+1:]

# 올바른 괄호 문자열 판별
def correct(arr):
    cnt = 0
    for i in arr:
        if i == '(':
            cnt += 1
        else: 
            cnt -= 1
            if cnt < 0:
                return False
    return True

 

문제3) 자물쇠와 열쇠(7.4%)

풀이방식 

2차원배열을 사용하여 90도 회전을 적용한 완전탐색을 구현하는 문제

 

 

다양한 풀이방법이 있겠지만 나의 경우에는 자물쇠의 크기를 모든 key를 돌 수 있도록 확장시켜줬다.

그리고 자물쇠는 확장된 자물쇠의 가운데에 둔다.

열쇠는 돌기부분은 1, 빈칸부분은 0으로 두고

자물쇠는 빈칸부분은 1(이후 확장된 부분도 1), 열쇠구명 부분은 0으로 두었다.

 

이후 key의 방향을 90도 회전시켜주며 한 방향에 대해서 완전탐색을 진행했다.

한번 탐색을 진행 후에 자물쇠와 키의 좌표가 겹치는 부분을 합산을 하고

새로운 자물쇠에서 자물쇠부분이 모두 1이 되면 true를 반환하고

모든탐색이 끝날때까지 반복되면 마지막에 false를 반환하도록 코드를 짯다.

 

 

• key를 90도 회전하는 함수 작성
•  - 열-> |((n-1)-행)|   &    행-> 열
• 행,열이 '자물쇠 + (열쇠의 크기-1) * 2' 인 새로운 자물쇠 2차원 배열(arr)을 선언
•  - key를 좌표의 처음(0,0)에서부터 돌리기 위함
•  모든좌표에 대해서 완전탐색 수행
• 1. key의 모든 방향(4)만큼 반복:
•    2. 새로운 자물쇠(arr)의 길이만큼 반복(i):
•       3. arr의 길이만큼 반복(j):
•          4. arr을 새로운 변수에 깊은복사로 할당 
•           - 이는 반복문을 돌때마다 각 자리를 합산하여 계산하기 위함
•          5. 새로운 자물쇠(new_lock)와 키(key)의 겹치는 좌표값은 합산을 하여 새로운 좌물쇠(new_lock)의 값을 변경
•          6. 새로운 좌물쇠(new_lock)의 기존 좌물쇠 부분의 좌표값을 확인하여 모두 1인경우에 true 리턴
• 7. 모든 탐색이 끝난 후 false 리턴

 

 

 

※ 6, 7, 15, 18~20번이 틀리는 경우

 

// 나의 경우였다.

 

틀리는 이유 :
열쇠의 이동범위를 틀림. -> 열쇠로 열 수 있는 경우가 아닌데 열 수 있다고 로직이 돌아감.
열쇠는 왼쪽과 위로는 (열쇠의 크기-1)까지 갈 수 있고, 오른쪽과 아래로는 (자물쇠의 크기-1)까지 갈 수 있음
이유는 열쇠와 자물쇠의 인덱스는 (0,0)부터 시작하고, 열쇠와 자물쇠의 크기는 다를 수 있기 때문입니다.
위 이동범위를 넘어서면 열쇠가 자물쇠에서 그냥 벗어나는 것입니다.
저는 열쇠 이동 범위를 범위를 상하/좌우 모두 (자물쇠 크기 -1)로 잡아줘서 틀렸네요

 

출처: https://programmers.co.kr/questions/16851 

 

 

 

[소스코드]

 

import copy

def solution(key, lock):

    # 2차원 배열(key) 90도 회전
    # 열-> |((n-1)-행)|, 행-> 열
    def rotate(k):
        rotate_key = [ [0] * len(k) for _ in range(len(k))]
        for i in range(len(k)):
            for j in range(len(k)):
                rotate_key[i][j] = k[j][abs(len(k)-1-i)]
        return rotate_key

    # 새로운 자물쇠 배열 선언
    result = False
    arr = [ [1] * (len(lock) + (len(key)-1)*2) for _ in range(len(lock) + (len(key)-1)*2)]
    for i in range(len(lock)):
        for j in range(len(lock)):
            arr[i+len(key)-1][j+len(key)-1] = lock[i][j]
    
    # 완전탐색
    for _ in range(4):
        key = rotate(key)
        
        for i in range(len(arr)-(len(key)-1)):
            for j in range(len(arr)-(len(key)-1)):
                new_lock = copy.deepcopy(arr)

                # 자물쇠와 키의 값의 합산
                for k1 in range(len(key)):
                    for k2 in range(len(key)):
                        new_lock[i+k1][j+k2] = new_lock[i+k1][j+k2] + key[k1][k2]
                
                # new_lock의 자물쇠부분 확인
                cnt = 0
                for l1 in range(len(lock)):
                    for l2 in range(len(lock)):
                        if new_lock[l1+len(key)-1][l2+len(key)-1] == 1:
                            cnt+=1
                            
                if cnt == len(lock)*len(lock):
                    result = True
                    return result
    
    return result

 

 

문제4) 가사 검색(정확성:34.4% 효율성:0.8%)

풀이방식 

문자열 문제 - 트라이 자료구조 또는 이분 탐색등 사용해야 효율성 통과

 

 

'해당 문제는 답지를 보면서 이해했다.'

혼자 풀었을 때는 선형방식으로 풀어서 효율성1~3번에서 막혔다.

 

카카오 해설

해설에서는 Trie문을 사용했는데 나의 경우에는 '이코테'책에서 나온 이분탐색 방법대로 진행했음.

 

 

• 각 단어를 길이에 따라서 나눔
• '?'가 접두어로 나오는 경우가 있으므로 문자열을 뒤집은 리스트를 별도로 생성
• 모든 리스트 정렬
• 각 쿼리에 대해서 이진 탐색을 수행
• replace를 사용해 '?'에 'a'를 넣었을 때와 'z'를 넣었을 때 사이의 문자열 개수를 bisect으로 구함

 

[소스코드]

 

from bisect import bisect_left, bisect_right

data = [[] for _ in range(10001)]
reversed_data = [[] for _ in range(10001)]
    
def count_by_range(data, left_value, right_value):
    right_index = bisect_right(data, right_value)
    left_index = bisect_right(data, left_value)
    return right_index - left_index
    
def solution(words, queries):
    answer = []

    for word in words:
        data[len(word)].append(word)
        reversed_data[len(word)].append(word[::-1])

    for i in range(10001):
        data[i].sort()
        reversed_data[i].sort()

    for q in queries:
        if q[0] == '?':    # 접두어가 '?'
            result = count_by_range(reversed_data[len(q)], q[::-1].replace('?','a'), q[::-1].replace('?','z'))
        else:
            result = count_by_range(data[len(q)], q.replace('?','a'), q.replace('?','z'))
        answer.append(result)
    return answer