카카오가 아닌 다른 회사에 다니고 있고
사내 알고리즘 강사로 활동 중인데
사내 알고리즘 시험에 맞춘 강의만 하다보니
사고가 갇히는 것 같아 심심해서 풀어보는
2020 카카오 인턴십 for Tech developers 문제풀이
문제는 아래 링크에서 풀어볼수 있다.
https://tech.kakao.com/2020/07/01/2020-internship-test/
2020 카카오 인턴십 for Tech developers 문제해설
2020년 카카오의 여름 인턴십이 시작 되었습니다.여름 인턴십의 첫번째 관문인 코딩 테스트가 2020년 5월 9일 오후 2시부터 6시까지 진행되었는데요, 온라인으로 진행되었기 때문에 코로나19로부터
tech.kakao.com
문제 :
스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.
이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
- 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
- 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
- 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
- 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인지 오른손인지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해 주세요.
제한사항 :
- numbers 배열의 크기는 1 이상 1,000 이하입니다.
- numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
- hand는
"left" 또는 "right" 입니다.
- "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
- 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.
입출력 예 :
접근법 전에
0) 문제를 보고 느낀점
① 시간제한이 안 써있다.
→ 매우 신선했다. 지금껏 봤던 알고리즘 테스트는 일반적으로 N이 10억 정도 주어지고 N^2의 로직을 사용할 경우 Time Out이 발생해 N 또는 N logN으로 줄이는 방법을 찾는게 중요했는데,
N이 1,000밖에 안 되는 문제에서 시간제한없이 코드를 제출해도 답만 맞으면 통과라고 나온다.
물론 당락에는 성능이 중요한 요소가 될 수도 있다. 효율성(아마도 성능인듯)에 따른 가점이 주어진다고 한다.
그래도 시간이 넘으면 바로 Time Out이 발생하던 문제에 익숙하다가 7문제를 빠르고 정확하게 구현해내는
이 시험이 신선하게 느껴졌다.
② 조금 더 실무스럽다
→ 정말 작은 차이에 지나친 의미부여를 하는 것일 수 있지만, 그동안 풀었던 알고리즘은 정답을 "입출력"하는게 중요했다.
그래서 실행시간을 줄이려고 Java의 경우 BufferedReader를 C++의 경우 cin.tie( )등을 통해 시간을 절약하려고 애쓰는데 사실 이는 알고리즘 로직과는 조금 동떨어진 스킬적인 부분이다.
그런데 이 문제는 입력이 매개변수로 주어져서 입력받을 필요가 없으며, 답을 String으로 return해 출력할 필요가 없다.
즉, 불필요한 부분에서 성능의 차이가 발생하는 것을 줄이고 로직 자체를 구현하는게 중요하다.
실무에서도 매개변수 또는 파일로 입출력이 주로 이뤄지기 때문에 조금 더 실무스럽다고 생각한다.
접근법 :
1) 어떻게 풀 것인가?
주어진 numbers를 그때 그때 판단하여 오른손으로 칠지 왼손으로 칠지 판단해야한다.
조건대로 구현만 하면 N의 시간복잡도로 풀 수 있고 numbers 배열의 크기가 1,000이하이기 때문에 특별한 로직이 필요하진 않다.
다만, 매번 왼손으로 칠지 오른손으로 칠지 선택할때 (2, 5, 8, 0 다이얼이 들어올때)
어떻게 코드로 구현할 것인지가 중요하다.
그래서 먼저 1,4,7 또는 3,6,9가 들어올 때는 무조건 각가 왼손, 오른손으로 고정하는 로직을 if else 또는 case 문으로 작성을 하고 2,5,8,0 로직을 작성해야한다.
이때, 왼손과 오른손의 위치는 계속해서 변화하므로 그 위치를 기록할 변수를 만들어서
매번 거리를 구하면 된다.
정말 코드의 성능만을 원할때는 복잡하지만 출발 다이얼 / 도착 다이얼 2차원 배열로 거리표를 미리 작성해놔도 된다.
12 * 12번 하드코딩이 필요한데 할까 하다가 총 7문제인 시험에서 의도하는 바가 아닌것 같아서 그냥 포기했고
일반적인 풀이법으로 예상되는
각 다이얼별 좌표를 구해놓고 상대위치를 매번 구해서 비교하는 식으로 풀이했다.
단순해보이지만 이렇게 풀이했을때 1초 내외로 풀이가 되고 가산점도 9점 얻었다고 뜬 것으로 봐서
이렇게 빨리 풀고 넘어가는게 효율적인 것 같다.
다이얼별 좌표를 부연설명하자면 아래 표와 같고
자세한 내용은 아래 코드로 구현되어있다.
| 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) |
| 0 (3,1) |
2) 시간복잡도
N이 1,000이므로 if else 조건이 많지만 성능상 무리는 없음.
시간복잡도 O(N). 테스트케이스가 어떻게 들어왔는지 모르겠지만
20개 테스트 케이스 평균 1ms 이내로 풀이 완료
3) 공간복잡도
N이 100개 이하이므로 고려하지 않음. 1MBytes 미만.
4) 풀면서 놓쳤던점
특별히 없음.
5) 이 문제를 통해 얻어갈 것
다이얼의 상대적 위치를 어떻게 코드(배열)로 표현할 것인가?
기본적인 구현하는 연습.
Java코드 : (github - https://github.com/subbak2/TIL/blob/master/2008 )
public class Solution {
// 문제에선 매개변수로 주어지는 부분
// (로컬에서 돌려보기위해 변수선언)
static int [] numbers = {1,3,4,5,8,2,1,4,5,9,5};
static String hand = "right";
// 좌표 클래스 r : row (행) / c : column(열)
static class location{
int r,c;
public location(int r, int c) {
this.r = r;
this.c = c;
}
}
static location[] map = new location[12]; // 숫자별 좌표를 담은 배열
static boolean rFlag = true; // 어느손잡이인지 판별용 : 오른손잡이 true / 왼손잡이 false
static int lLoc = 10; // *을 임의로 10으로 변환
static int rLoc = 11; // #을 임의로 11으로 변환
public static void main(String[] args) {
String answer = "";
// 만약에 왼손잡이이면 flag를 false로
if (hand.equals("left")) {
rFlag = false;
}
// 각각 다이얼 숫자별 좌표를 초기세팅
map[0] = new location(3,1);
map[1] = new location(0,0);
map[2] = new location(0,1);
map[3] = new location(0,2);
map[4] = new location(1,0);
map[5] = new location(1,1);
map[6] = new location(1,2);
map[7] = new location(2,0);
map[8] = new location(2,1);
map[9] = new location(2,2);
map[10] = new location(3,0);
map[11] = new location(3,2);
// numbers의 길이만큼 반복문 실행
int len = numbers.length;
for (int i=0; i<len; i++) {
int num = numbers[i];
// 1. num이 1,4,7일 경우 무조건 왼손
if (num %3 == 1) {
lLoc = num;
answer = answer.concat("L");
}
// 2. num이 3,6,9일 경우 무조건 오른손
else if (num %3 == 0 && num != 0) {
rLoc = num;
answer = answer.concat("R");
}
// 3. num이 2,5,8,0일 경우 판별
else {
answer = answer.concat(addAnswer(num));
}
}
System.out.println(answer);
}
// 가운데 다이얼일경우 판별하는 함수
static String addAnswer(int num) {
int lDis = distance(map[num], map[lLoc]); // 왼손에서의 거리
int rDis = distance(map[num], map[rLoc]); // 오른손에서의 거리
// 1. 오른손잡이
if (rFlag) {
// 1) 왼손이 짧을때만 왼손으로
if (lDis<rDis) {
lLoc = num;
return "L";
}
// 2) 나머지는 오른손으로
else {
rLoc = num;
return "R";
}
}
// 2. 왼손잡이
else {
// 1) 오른손이 짧을때만 오른손으로
if (rDis<lDis) {
rLoc = num;
return "R";
}
// 2) 나머지는 왼손으로
else {
lLoc = num;
return "L";
}
}
}
// 거리 구하는 함수 y좌표 절대값 차이 + x좌표 절대값 차이
static int distance(location l1, location l2) {
int dis1 = l1.r - l2.r;
int dis2 = l1.c - l2.c;
if (dis1<0) dis1 *= -1;
if (dis2<0) dis2 *= -1;
return dis1 + dis2;
}
}