https://careers.kakao.com/2020-intern
2020 kakao internship
2020 kakao internship
careers.kakao.com
오늘은 카카오 인턴십 코딩테스트 시험을 치렀습니다.
이번이 카카오 3번 째 코딩테스트 도전인데 그동안의 공부가 효과가 있었는지 5문제 모두 맞았습니다.
총 5문제가 출제되었습니다.
저작권 문제로 문제를 전부 올릴 수 없어 간단한 문제 설명 및 풀이만 작성하였습니다.
댓글로 이메일 남겨주시면 문제 보내드리겠습니다.
[1번 문제]
아래와 같은 전화 키패드가 있습니다.
1 2 3
4 5 6
7 8 9
* 0 #
이 전화 키패드에서 왼손 엄지와 오른손 엄지만을 이용해 숫자만을 입력할 때 입력의 시작에서
왼손 엄지는 *에 오른손 엄지는#에 위치하며 키패드에 좌측에 존재하는 숫자(1,4,7)를 입력할 때는 왼손으로
키패드 우측에 존재하는 숫자(3,6,9)를 입력할 때는 오른손으로만 입력하며 중간에 있는 숫자(2,5,8,0)를 입력할 때는 왼손과 오른손 중 더 가까운 위치에 있는 손가락으로 입력합니다.
만약 왼손과 오른손의 거리가 같다면 왼손잡이는 왼손으로 오른손잡이는 오른손으로 입력합니다.
입력으로 순서대로 입력해야 하는 숫자가 배열의 형태로 주어지고 왼손잡이인지 오른손잡이인지를 문자열을 통해 알려줍니다.
출력으로는 각 번호를 누른 손가락이 왼손인지 오른손인지 순서대로 나타내는 문자열을 반환합니다,
[1번 문제풀이]
2차원 배열로 현재 왼손과 오른손의 위치를 저장하고
입력해야 하는 숫자가 왼쪽(1,4,7)이면 왼손위치를 해당 번호로 이동시키고
입력해야 하는 숫자가 오른쪽(3,6,9)이면 오른손 위치를 해당 번호로 이동시킵니다.
만약 입력해야 하는 숫자가 중앙이면 왼손과 오른손의 거리를 각각 계산하고
같으면 왼손잡이인지 오른손잡이인지를 검사해 해당하는 손을 이동시키고
아니라면 더 가까운 손을 이동시킵니다.
[2번 문제]
+,-,*와 숫자로 이루어진 문자열이 입력으로 주어집니다.
해당 문자열은 중위 표기법으로 계산이 가능한 형식으로 주어집니다.
사칙연산에서는 기본적으로 * 가 연산 우선순위를 가지고 +,-가 같은 우선순위를 가지며
앞에서부터 계산합니다.
2번 문제에서는 +,-,*의 우선순위를 바꿀 수 있으며 +,-,*는 같은 우선순위를 가질 수 없습니다.
문자열이 주어졌을 때 +,-,*의 우선순위를 변경하여 만들 수 있는 가장 큰 절댓값을 구하는 문제입니다.
[2번 문제풀이]
문자열을 파싱하여 +,-,*을 추출하여 연산자 배열을 만들고
+,-,*을 모두 콤마(,)로 바꾸어 문자열을 콤마 기준으로 split 하여 숫자 배열을 만들었습니다.
그 후 연산자 배열을 3번 순회하며 우선순위별로 계산하였습니다.
+,-,* 의 우선순위를 정하는 경우의 수는 총 6가지로
+ - *
+ * -
* + -
* - +
- + *
- * +
가 있으며 우선순위별로 계산을 통해 값을 추출하여 절댓값이 가장 큰 값을 반환하였습니다.
예를 들어 "100-200*300-500+20" 이런 문자열이 입력값으로 주어지면
연산자 배열은 - * - + 가 되고
숫자 배열은 100 200, 300 500 20이 됩니다.
우선순위가 - + * 인 경우에
연산자 배열의 첫 번째 순회에서
100- 200 연산을 가장 먼저 실행하고 결괏값은 -100
연산자 배열은 * - +가 되며
숫자 배열은 -100 300 500 20이 됩니다.
그 후 -을 만나는 1번째 인덱스의 계산은 300-500을 실행하게 됩니다.
연산자 배열은 * +가 되며
숫자 배열은 -100 -200 20이 됩니다.
연산자 배열을 끝까지 순회하였으므로
두 번째 순회를 시작합니다.
두 번째 순회에서는 +을 먼저 연산하기 때문에
-200 + 20이 실행되며
연산자 배열은 *가
숫자 배열은 -100 -180이 됩니다.
마지막 순회에서는 *가 실행되어
-100 * -180이 계산되며 순회가 종료되어
| 18000 | 이 결과가 됩니다.
우선순위 종류 6가지를 위처럼 계산하여 가장 큰 값을 반환하였습니다.
[3번 문제]
문자열 배열이 입력으로 주어집니다.
각 문자열은 중복될 수 있으며 중복되는 문자열은 같은 종류로 취급됩니다.
문자열의 모든 종류를 포함하는 가장 짧은 배열 길이를 구하는 문제였습니다.
[3번 문제풀이]
문자열 번호
1
2
3
4
5
6
7
8
문자열 이름
AAA
BBB
BBB
AAA AAA
CCC
DDD
AAA
배열 길이를 구하기 전 몇 종류의 문자열이 존재하는지 먼저 계산한 후 발견 순서에 따라 0~N-1(문자열 종류 개수)까지의 번호를 매겨주었습니다. 해당 작업은 MAP을 통하여 이루어졌습니다.
이후에 N 크기 만큼의 정수 배열은 선언후 문자열 배열을 순회하며 위에서 선언한 정수 배열이 각 문자열이 마지막에 나온 인덱스를 저장하도록 하였습니다. 예를 들어 AAA 문자열은 0번의 번호를 부여받았고 정수배열의 0번 인덱스는 AAA를 상징하게 됩니다. 문자열 순회 시 정수배열 0번 인덱스의 값은 0, 3, 4, 7에서 각각 업데이트됩니다.
문자열을 순회하며 모든 문자열이 나왔을 때 정수 배열의 가장 작은 값과 가장 큰 값의 차이를 구하였습니다.
해당 차이가 모든 문자열을 포함하는 길이가 되며 이 길이가 가장 짧을 때의 정수배열에서 가장 작은 값과 가장 큰 값을 저장하며 문자열 배열을 끝까지 순회한 후 저장된 두 개의 값을 반환하였습니다.
[4번 문제]
N*N 크기의 배열이 주어지며 0, 0에서 출발하여 N-1, N-1에 도착할 때 가지의 최소비용을 구하는 문제입니다.
N*N 배열은 0 혹은 1이 주어지며 0은 갈 수 있는 길 1은 갈 수 없는 길입니다.
배열 내에서의 이동은 방향을 가지고 있으며 방향을 변경할 수 있습니다.
직선으로 이동할 때는 100의 비용이 발생하며 방향을 변경할 때는 500의 비용이 발생합니다.
N-1, N-1으로 이동할 때 가장 적게 드는 비용이 얼마인지 반환해야 하는 문제입니다.
[4번 문제 풀이]
배열의 각 칸을 방문하기 전 4방을 검사하여 각 칸으로 이동했을 때의 비용을 계산합니다.
각 칸이 한 번도 방문 되지 않았거나 이전에 해당 칸으로 이동했을 때의 최소 비용보다 현재 이동 비용이 저렴할 경우
해당 칸의 숫자를 현재 이동비용으로 변경한 후 큐에 해당 칸의 col, row값을 저장합니다.
큐를 순회하며 더는 이동할 수 있는 지점이 존재하지 않을 때 n-1, n-1의 값을 출력합니다.
[5번 문제]
방마다 번호가 존재하며 각 방은 서로 연결된 통로가 하나씩만 존재합니다.
모든 방은 연결되어있으며 가장 먼저 들어가야 하는 방은 0번 방입니다.
각방은 이전에 필수로 방문해야 하는 방이 있을 수 있습니다. 모든 방은 횟수 제한 없이 방문할 수 있습니다.
필수로 방문해야 하는 방을 아직 방문하지 않으면 해당하는 방을 방문할 수 없습니다.
모든 방의 개수와 각 방이 어떤 방과 연결되어 있는지 그리고 필수로 방문해야 하는 방이 배열로 주어졌을 때
모든 방을 방문할 수 있는지 반환하는 문제입니다.
[5번 문제 풀이]
트리구조로 변경하여 문제 풀이를 진행하였습니다.
노드별로 부모 노드 번호를 저장하는 배열과 노드별로 필수로 방문해야 하는 노드 번호를 배열로 저장하였습니다.
노드를 깊이별로 큐에 차례로 넣어준 후 큐를 순회하며 해당 노드의 부모 노드와 필수방문 노드의 방문 여부를 판단하여 방문한 경우에는 pop을 하고 방문하지 못하면 pop 한 후 해당 값을 다시 큐에 넣어주었습니다.
큐가 한 바퀴 순회하였을 때 하나의 노드도 방문하지 못한 경우에 false를 반환하였고 모든 노드에 방문하여 큐가 볐을 때 true를 반환하였습니다.
[후기]
1번 문제를 30분 동안 풀었는데 생각보다 오래 걸려서 다 맞진 못하겠다고 생각했는데 4번 문제가 익숙한 유형의 문제여서 빨리 푼 덕분에 모든 문제를 풀 수 있었던 거 같습니다.
2번 문제의 경우 원래 C++로 코테를 진행하지만, 문자열에 한해서 핸들링이 편한 JAVA를 이용하였습니다.
5번 문제의 효율성 부분에서 마지막 채점에서 시간 초과가 발생하였습니다.
해당 예제는 20만 개의 노드가 모두 1 깊이로 이루어져 있고 필수 방문 노드가 각 노드의 역순으로 이루어져 있는
것으로 추정되어 노드를 방문하지 못하는 경우에 방문하지 못하는 이유가 되는 노드를 한 번만 더 검사하도록 풀었더니 효율성 부분에서 만점을 받을 수 있었습니다.
2달간 열심히 풀었더니 실력이 많이 오른 것 같습니다. 그전 카카오 코테에서는 7문제 기준 3.5솔 5문제 기준 3솔을 했는데 이번에 처음으로 올솔을 해서 기분이 좋았습니다.
최종합격 될지 모르지만, 열심히 인터뷰 준비해야 할 것 같습니다.
코테 보신 모든 분들 수고 많으셨습니다!
'Algorithm > Coding Test' 카테고리의 다른 글
| 2020 Dev-Matching: 웹 백엔드 코딩테스트 후기 (3) | 2020.04.28 |
|---|
