오늘의 스터디 문제 목록
키패드 누르기
스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.
이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
- 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
- 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
- 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
- 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
- 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
function solution(numbers, hand) {
let useHand = "";
let left_location = "*"; //? 왼손 위치
let right_location = "#"; //? 오른손 위치
for (let i = 0; i < numbers.length; i++) {
if (numbers[i] === 1 || numbers[i] === 4 || numbers[i] === 7) {
//! 1 4 7 왼손
left_location = numbers[i]; // 위치 바꿔 주기
numbers[i] = "L";
} else if (numbers[i] === 3 || numbers[i] === 6 || numbers[i] === 9) {
//! 3 6 9 오른손
right_location = numbers[i]; // 위치 바꿔 주기
numbers[i] = "R";
} else {
//! 2 5 8 0일 때
useHand = distance_fuc(numbers[i], left_location, right_location, hand);
// 숫자를 누를 손이 왼손일 경우에 왼손 위치를 바꿔 줌
if (useHand === "L") {
left_location = numbers[i];
} else {
// 오른손일 경우에 오른손 위치 바꿔 줌
right_location = numbers[i];
}
numbers[i] = useHand;
}
}
return numbers.join("");
}
// destination = 눌러야하는 숫자
// leftH = 현재 왼손 위치
// rightH = 현재 오른손 위치
// myhand = 어느 손잡이인지
function distance_fuc(destination, leftH, rightH, myhand) {
const keypad = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
["*", 0, "#"],
];
let dtn = [];
let left = [];
let right = [];
// 눌러야 할 숫자 5의 위치 [1, 1]
// 왼손의 위치가 4일 때 위치 [1, 0]
// 0 + 1 = 1차이
// 눌러야 할 숫자 5의 위치 [1, 1]
// 왼손의 위치가 4일 때 위치 [0, 2]
// 1 + (-1) = 2차이
// 마이너스로 나올 수 있으므로 Math.abs 절대값으로 변환해서 거리 비교
//! 목적지 위치, 왼손 위치, 오른손 위치 구하기
for (let i = 0; i < keypad.length; i++) {
//? 1차원으로 돌기
for (let j = 0; j < keypad[i].length; j++) {
//? 2차원 돌기
if (keypad[i][j] === destination) {
// 목적지 위치
dtn.push(i, j);
}
if (keypad[i][j] === leftH) {
// 왼손 위치
left.push(i, j);
}
if (keypad[i][j] === rightH) {
// 오른손 위치
right.push(i, j);
}
}
}
//! 두 손의 거리 구하기
// (목적지 0번째 - 왼쪽0번째) + (목적지 1번째 - 왼쪽 1번째)
let left_distance = Math.abs(dtn[0] - left[0]) + Math.abs(dtn[1] - left[1]);
// (목적지 0번째 - 오른쪽0번째) + (목적지 1번째 - 오른쪽 1번째)
let right_distance =
Math.abs(dtn[0] - right[0]) + Math.abs(dtn[1] - right[1]);
//! 더 짧은 거리 사용한 손으로 리턴해 주기
if (left_distance === right_distance) {
return myhand[0].toUpperCase();
} else if (left_distance < right_distance) {
return "L";
} else {
return "R";
}
}
절대값으로 변환해야 되는 걸 간과하고 있다가 왜 리턴이 이상하게 되지...? 라고 생각했던 문제 디버깅 돌려보니까 완벽한 나의 실수였다! 카카오 문제는 항상 구글링의 힘을 빌렸었는데 이번엔 뭔가 오기가 생겨서 아득바득 열심히 풀어 보려고 했고 구글링을 하지 않았다!! 처음에 어떻게 풀어야 할지 막막했는데 내 힘으로 한번 풀어보니 뿌듯하기도 하고 재미있기도 해서 테스트케이스가 막히는 게 두렵지 않게 됐다. (두렵지 않을뿐이지 좋다곤 안 했다.) 스터디를 진행하면서 코드리뷰 중에 정호님을 통해서 거리를 구하는 것이 공식이 있었다는 것을 알게 되었다 내가 풀었던 방식 또한 맨하탄의 거리 계산이었다는 것이다!
[맨하탄 거리 계산]
|x1 -x2| + |y1-y2| = 거리정호님의 코드를 보고 공식이었다는 설명을 듣고 나서 이 문제에 대해서 완벽하게 파악할 수 있었다. 그리고 생각보다 별거 아니었던 문제였던 것까지도...
function solution(numbers, hand) {
// L - 1,4,7
// R - 3,6,9
// L R 중 가까운 놈 2,5,8,0
let posL = "*";
let posR = "#";
const result = [];
for (let num of numbers) {
switch (num) {
case 1:
case 4:
case 7:
result.push("L");
posL = num;
break;
case 3:
case 6:
case 9:
result.push("R");
posR = num;
break;
case 2:
case 5:
case 8:
case 0:
let distL = getDist(posL, num);
let distR = getDist(posR, num);
if (distL === distR) {
if (hand === "left") {
result.push("L");
posL = num;
} else {
result.push("R");
posR = num;
}
} else {
if (distL < distR) {
result.push("L");
posL = num;
} else {
result.push("R");
posR = num;
}
}
break;
default:
break;
}
}
return result.join("");
}
// num의 2차원배열 인덱스 리턴
function getIdx(num) {
const arr = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
["*", 0, "#"],
];
switch (num) {
case 1: case 2: case 3:
return [0, arr[0].indexOf(num)];
case 4: case 5: case 6:
return [1, arr[1].indexOf(num)];
case 7: case 8: case 9:
return [2, arr[2].indexOf(num)];
case "*": case 0: case "#":
return [3, arr[3].indexOf(num)];
default: break;
}
}
// present ~ target 거리 계산
function getDist(present, target) {
const presentIdx = getIdx(present);
const targetIdx = getIdx(target);
return Math.abs(presentIdx[0] - targetIdx[0]) + Math.abs(presentIdx[1] - targetIdx[1]);
}제일 달랐던 민혁님의 코드 case로 하니 내가 적었던 if 괄호 지옥보다 훨씬 깔끔해 보이고 보기 좋았으며 코드 한 줄 한 줄이 어떤 의미를 내포하는지 알 수 있어서 좋았다. 나도 다음에 swich 써 봐야징 ㅎㅎㅎㅎ!! 항상 습관적으로 if를 갈기게 되는데... 많은 케이스로 나눌 수 있으면 되도록 case로 하는 방법이 눈에 잘 들어오고 깔끔한 것 같다.
숫자 짝꿍
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.
숫자 짝꿍 11~15 Test Cacs 시간초과 실패 코드
function solution(X, Y) {
// filter를 쓰기 위해 문자열 배열로 변환
X = [...X]; // or X = [...X]
Y = [...Y]; // or Y = [...Y]
// 1. 교집합 요소가 하나도 없을 경우
let same = X.filter((ele) => Y.includes(ele));
if (same.length === 0) return "-1";
// 2. 교집합 요소가 모두 0일 경우
if (Number(same.join("")) === 0) return "0";
let result = [];
// X, Y 이중 반복문 돌려서 같으면 Push 후, 해당 요소 삭제
for (let i = 0; i < X.length; i++) {
for (let j = 0; j < Y.length; j++) {
if (X[i] === Y[j]) {
result.push(X[i]);
//! delete 사용 시, 특정 배열 요소를 empty로 변경한다
delete X[i];
delete Y[j];
}
}
}
return result.sort((a, b) => b - a).join("");
}
solution("12321", "42531");X, Y 가 문자열로 들어오기 때문에 배열로 바꿔주는 부분을 spreed 연산자를 사용해서 변환해 주었지만 처음에는 저것 마저도 split을 썼었다. 이번 스터디 과제를 하면서 알고리즘에 대한 고안보다는 "시간을 어떻게 줄일 것인가..."를 더 중점적으로 하다보니 시간을 많이 잡아먹었다. 시간 복잡도를 고려할 때가 됐다는 건가?,,, 시간 복잡도에 대한 언급이 나왔으니 이를 정리하고 가겠다.
해당 시간복잡도 요점 사진과 이를 정리한 블로그를 통해 확인해 보자.
시간복잡도에 대한 것을 살펴보니 순회하며 값을 리턴하는 메서드(?)들을 내가 자주 쓰고 있었다. 특히 나는 이중for문을 자주 사용하는 편인데 이는 배열을 순회하면서 그 안에서 또 순회하는 모양을 띄고 있으므로 효율성 부분에서는 이중for문을 사용을 지양해야겠다고 생각했다.
그런데도 효율성을 확인하는 테스트 케이스가 11~15였으니 시간초과로 실패하는 게 당연했다. 이중for문을 저렇게 대놓고 썼으니... 그럴만도 하다. 처음에는 시간복잡도에 대한 개념이 없어서 이것저것 모든 메서드를 의심했었다. filter구나... sort인가?... 하다가 제일 큰 이중for문은 정작 건드리지도 않아서 시간이 무지하게 오래 걸렸다. 나중에서야 시간복잡도를 제대로 파악하고 나서 이중for문을 다른 방식으로 풀었더니 해결할 수 있었다.
성공 코드
function solution(X, Y) {
X = [...X]; //! ['1', '2', '3', '2', '1']
Y = [...Y]; //! ['4', '2', '5', '3', '1']
let result = "";
for (let i = 0; i <= 9; i++) {
//! 2 돈다고 치셈
let x = X.filter((ele) => Number(ele) === i).length; //! 2
let y = Y.filter((ele) => Number(ele) === i).length; //! 1
result += String(i).repeat(Math.min(x, y)); //! 1번 2가 찍힘
}
//? 1. 짝꿍 없을 경우
if (result === "") return "-1";
//? 2. 모두 0인 경우
if (Number(result) === 0) return "0";
//? result = '123' / 정렬돼서 나와야 됨, 문자열 상태니까 다시 배열로 만들어 줌
result = [...result];
//! 정렬 순서가 문자열 유니코드 포인트를 따르기 때문에 Number 타입으로 정렬
return result.sort((a, b) => Number(b) - Number(a)).join("");
}
solution("12321", "42531");for문을 없애고 filter를 통해 X, Y에서 각 요소가 몇 번 나오는지 구해준 다음에 X, Y에 재할당 후, 둘 중 더 작은 수만큼 문자열 형태로 해당 수를 반복하게 해 주었다. 짝꿍이 아예 없다면 filter 부분에서 애초에 빈 배열로 나오기 때문에 처음에 할당해 줬던 '' 빈문자열 형태로 나오게 되므로 위와 같이 해 주었으며, 0도 마찬가지이다.
function solution(X, Y) {
// 객체를 만들고
// 0~9 까지의 인덱식하고 개수별로 카운트를 해줌
// 중복된 값이 있으면 그 값을 배열에 넣고 인덱스에 -1을 해줌
// 배열에 있는 값을 sort하고 리턴
const arr = [];
const objX = {};
for(value of X){
// 비트 연산자 |
objX[value] = (objX[value] | 0) + 1;
}
for(value of Y){
if(objX[value]){
arr.push(value);
objX[value]--;
}
}
// console.log(objX);
// console.log(arr);
let result = arr.sort((a,b)=>b-a).join('');
if(result){
if(+result === 0) return '0';
return result;
// 이게 문제였네
// return String(+result);
}
return '-1'
}신기했던 효근님 Number(result) 대신 +로 해 주신 게 인상 깊었고 객체로 풀었던 코드이다.
과일 장수
과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다. 한 상자에 사과를 m개씩 담아 포장합니다. 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다. 과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다. (사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)
예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.
- (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8
사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.
과일 장수 10~15 Test Cacs 시간초과 실패 코드
function solution(k, m, score) {
// 사과 한 박스 가격 = p(최저 사과 점수) * m(사과 개수)
// 1. Math.floor(score.length / m) 해서 몇 박스 만들 건지 일단 구해 준 다음에
const box = Math.floor(score.length / m);
// 2. 사과 품질 정렬해 줌
score.sort((a, b) => b - a);
// 3. 박스로 나눠 줌
let boxSet = [];
for (let i = 1; i <= box; i++) {
boxSet.push(score.splice(0, m));
}
//! 이렇게 들어온 상태임 boxSet = [[1, 1, 2], [2, 2, 2], [4, 4, 4], [4, 4, 4]]
let profit = 0;
for (let x = 0; x < boxSet.length; x++) {
//! [1, 1, 2]부터 돌게 됨
profit += Math.min(...boxSet[x]) * m;
}
return profit;
}
solution(4, 3, [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]);이 코드 또한 시간 초과로 실패한 코드 박스로 나눠 주는 부분을 for문 앞에서 splice를 썼기 때문인 것 같아서 해당 부분 개선하고자 for문 한 번으로 끝낼 수 있는 방법으로 풀었더니 해결되었다.
성공 코드
function solution(k, m, score) {
// 사과 한 박스 가격 = p(최저 사과 점수) * m(사과 개수)
// 1. Math.floor(score.length / m) 해서 몇 박스 만들 건지 일단 구해 준 다음에
const box = Math.floor(score.length / m);
// 2. 사과 품질 정렬해 줌
score.sort((a, b) => b - a);
//! 최하품 사과 인덱스 사과 개수 -1로 하면 각 상자의 마지막 요소가 나오게 된다.
//! 정렬을 이미 해 줬기 때문에 -1번째는 최하품 사과임
let lowest = m - 1;
let profit = 0;
for (let x = 1; x <= box; x++) {
profit += score[lowest] * m; // 최하품 사과 점수 * 사과 개수
lowest += m; // 다음 박스로 넘어가려면 사과 개수를 더해 줌
}
return profit;
}
solution(4, 3, [6, 5, 5, 4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]);박스로 포장해 주는 건 +m(한 박스 당 들어가는 사과의 개수)를 해 주었다.
function solution(k, m, score) {
// 작은게 섞이면 작은거 값으로 하니깐 최대한 큰것만 담아야함
// score를 sort하고
// m만큼 배열에 넣고
// 배열의 최소값 * 배열의 길이
const arrs = [];
const sortedScore = score.sort((a,b)=>a-b);
let result = 0;
while(true){
// 더 이상 상자가 나오지 않으면 종료
if(Math.floor(sortedScore.length / m) === 0){
break;
}
const tempArr = [];
for(let i = 0; i < m; i++){
tempArr.push(sortedScore.pop());
}
arrs.push(tempArr);
}
for(arr of arrs){
// 마지막 값이 최소 값
result += m * arr.slice(-1);
}
return result;
}while로 푼 효근님 코드 while 조건을 true로 주고 박스를 더 이상 만들 수 없는 경우는 m으로 나누었을 때 몫이 1로 나오지 않는 것이니까 0으로 나온다면 해당 while문을 빠져 나오게 해 두신 방법이 좋아서 가지고 왔다.
