[KAKAO] 2020 카카오 인턴십

2020 카카오 인턴십 코딩테스트

2021-6-23 & 2021-6-28 알고리즘 스터디 (오전10시~오후1시)

 

카카오 공식 해설

https://tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

 

 

문제1) 키패드 누르기(25.9%)

풀이방식 

2차원배열 형태를 사용하여 해당 위치를 이용해 두점 사이의 거리를 비교하는 문제

 

• 먼저 왼손과 오른손의 위치를 저장할 변수(left, right)를 선언
• 키패드의 숫자들을 2차원 배열의 형태로 만들어줌
• 1,4,7이나 3,6,9가 나왔을 경우에는 해당손의 위치를 변경해주고 answer에 해당손('L'or'R')을 더해줌
• 2,5,8,0의 숫자가 나왔을 경우에는 두점사이의 거리(distance)를 구해주어 조건에 맞게 answer에 더함

 

 

소스코드

 

def distance(keypad, dis1, dis2):
    return abs(dis1[0]-dis2[0]) + abs(dis1[1]-dis2[1])

def solution(numbers, hand):
    answer = ''
    left = '*'
    right = '#'

    keypad = {
        1:[0,0], 2:[0,1], 3:[0,2],
        4:[1,0], 5:[1,1], 6:[1,2],
        7:[2,0], 8:[2,1], 9:[2,2],
        '*':[3,0], 0:[3,1], '#':[3,2]}
        
    for idx,i in enumerate(numbers):

        if i==1 or i==4 or i==7:
            left = i
            answer += 'L'
            
        elif i==3 or i==6 or i==9:
            right = i
            answer += 'R'
            
        else:
            left_dis = distance(keypad, keypad[left],keypad[i])
            right_dis = distance(keypad, keypad[right], keypad[i])
            if left_dis < right_dis:
                left = i
                answer += 'L'
            elif right_dis < left_dis:
                right = i
                answer += 'R'
            elif left_dis == right_dis:
                if hand == 'right':
                    right = i
                    answer += 'R'
                else:
                    left = i
                    answer += 'L'
    return answer

 

 

 

 

문제2) 수식 최대화(23.1%)

 

풀이방식

식의 숫자,기호부분을 구별하여 별도로 저장한 후 우선순위에 따라 기호의 인덱스를 기억해 앞뒤연산을 해줌

 

• expression(식)을 기호부분과 숫자부분으로 나누어 각자 배열로 저장
• 기호부분은 순열(permutations)을 사용하여 모든경우의 수를 구함
• 우선순위의 기호의 인덱스[k]를 구한후 해당 인덱스와 같은 숫자부분[k]과 그다음 인덱스의 숫자부분[k+1] 연산을 수행
• 연산수행후 숫자부분[k]의 값을 바꿔주고 사용한 기호[k]와 숫자[k+1]를 배열에서 삭제
• 결과값에 절댓값(abs)를 씌워주고 최대값으로 answer을 갱신

 

 

※ 주의할점 ※

shallow copy(얕은 복사)

s_cal, s_num 할당부분에서 변수간대입(ex) s_cal = cal)을 사용하게 되면 값이 할당되는게 아니라 같은 메모리 주소를 바라보게됨

즉, s_cal을 변경하게되면 cal도 변경이 되는 현상이 일어나서 정닶이 첫번쨰 이후로는 제대로 나오지 않음

s_cal에 다른값을 할당하지 않는 이상은 같은 메모리주소를 공유함

 

s_cal = cal[:] 처럼 슬라이싱을 통해 값을 할당하면 새로운 id를 부여받게되어 서로 영향을 받지 않게됨

하지만 다중리스트인 경우에는,

ex) arr[[1,2],[3,4]] 인경우 arr2 = arr[:]를 했을때, arr2와 arr은 다른 주소값을 가지지만 arr2[0]과 arr[0]은 같은 주소값을 가지게 됨

이또한 재할당을 하게된다면 다른 주소값을 가지게되어 문제가 되지 않음

 

deep copy(깊은 복사)

내부의 객체들까지 모두 새롭게 copy해주는 모듈

import copy

arr2 = copy.deepcopy(arr) 

 

결론, 해당문제에서는 단일리스트이므로 s_cal = cal[:]을 통한 슬라이싱 할당을 하거나 deep copy를 이용해야 함

 

 

// 이것때매 마지막에 시간을 꽤 잡아먹었다. 확실히 알아두고 넘어가자.