728x90
21_inequalityNumber
아래와 같은 과정을 거쳐 부등호 수(inequalityNumber)를 만들 수 있습니다.
- 최대 9개의 부등호(<, >)가 주어집니다.
- 부등호의 좌우에는 0부터 9사이의 숫자가 한 번씩만 들어가야 합니다.
- 부등호를 만족하는 숫자의 조합을 차례대로 이어 붙여 만든 정수를 부등호 수라고 한다.
부등호 기호들을 입력받아 부등호를 만족하는 최대 부등호 수와 최소 부등호 수의 차이를 리턴해야 합니다.
입출력 예시
let output = inequalityNumber('<');
console.log(output); // --> 88 (89 - 01)
output = inequalityNumber('< >');
console.log(output); // --> 876 (897 - 021)
output = inequalityNumber('> < >');
console.log(output); // 더보기
const inequalityNumber = function (signs) {
const aux = (idx, signs, nums, digits, isVisited) => {
if (idx === signs.length) {
// 부등호 수를 만든 경우
return parseInt(nums.join(''))
}
const sign = signs[idx]
for (let i = 0; i < digits.length; i++) {
// 숫자를 차례대로 검토한다.
// max를 구할 때는 9부터, min을 구할 때는 0부터
const right = digits[i]
// 이전 단계에서 사용한 숫자인 경우 스킵
if (isVisited[right]) continue
// 첫번째 숫자가 아닌 경우에는 조건이 중요하다.
if (idx >= 0) {
// 항상 바로 직전의 숫자와 비교하면 된다.
const left = nums[nums.length - 1]
if (sign === '<' && left >= right) continue
if (sign === '>' && left <= right) continue
}
// 조건을 만족하거나 첫번째 숫자인 경우
isVisited[right] = true
const target = aux(idx + 1, signs, nums.concat(right), digits, isVisited)
if (target !== undefined) {
// 부등호 수를 이미 찾은 경우 탐색을 더 할 필요가 없다.
return target
}
// 탐색에 실패한 경우, 시도한 숫자의 상태(사용중)를 원래대로(사용안함) 바꿔놔야 한다.
isVisited[right] = false
}
return undefined
}
signs = signs.split(' ')
const digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
// arr.reverse()는 in-place 함수(데이터 직접 변경)이므로 min과 max의 순서는 중요하다.
const min = aux(-1, signs, [], digits, Array(10).fill(false))
const max = aux(-1, signs, [], digits.reverse(), Array(10).fill(false))
return max - min
}
22_rotateMatrix
문제
2차원 N x N 배열을 시계 방향으로 90도 회전시킨 배열을 리턴해야 합니다.
입출력 예시
const matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16],
];
console.log(matrix[0][0]); // --> 1
console.log(matrix[3][2]); // --> 15
const rotatedMatrix = rotateMatrix(matrix);
console.log(rotatedMatrix[0][0]); // --> 13
console.log(rotatedMatrix더보기
const rotateMatrix = function (matrix, rotateNum = 1) {
// rotateNum 이 0일 수 있으므로 아래와 같은 초기화는 지양해야 함
// rotateNum = rotateNum || 1
const N = matrix.length;
// 빈 배열을 입력받을 수 있다.
const M = matrix[0] && matrix[0].length;
rotateNum = rotateNum % 4;
// 회전하지 않는다.
if (rotateNum === 0) return matrix;
const rotated = [];
// 홀수번 회전 시 M x N, 짝수번 회전 시 N x M
const RC = rotateNum % 2 === 1 ? [M, N] : [N, M];
for (let row = 0; row < RC[0]; row++) {
rotated[row] = [];
for (let col = 0; col < RC[1]; col++) {
if (rotateNum === 1) rotated[row][col] = matrix[N - col - 1][row];
else if (rotateNum === 2)
rotated[row][col] = matrix[N - row - 1][M - col - 1];
else rotated[row][col] = matrix[col][M - row - 1];
}
}
return rotated;
};
23_spiralTraversal
문제
2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다.
입출력 예시
let matrix = [
['A', 'B', 'C'],
['D', 'E', 'F'],
['G', 'H', 'I'],
];
let output = spiralTraversal(matrix);
console.log(output); // --> 'ABCFIHGDE'
matrix = [
['T', 'y', 'r', 'i'],
['i', 's', 't', 'o'],
['n', 'r', 'e', 'n'],
['n', 'a', 'L', ' '],
];
output = spiralTraversal(matrix);
console.log(output); // -더보기
const spiralTraversal = function (matrix) {
// 각 방향마다 row와 col의 변화를 저장
const RIGHT = [0, 1];
const DOWN = [1, 0];
const LEFT = [0, -1];
const UP = [-1, 0];
// 각 방향을 위한 lookup table
const MOVES = [RIGHT, DOWN, LEFT, UP];
const M = matrix.length;
const N = matrix[0].length;
const isValid = (row, col) => row >= 0 && row < M && col >= 0 && col < N;
let cnt = 0;
let row = 0,
col = -1;
let direction = 0;
let result = '';
while (cnt < M * N) {
const move = MOVES[direction];
const [rd, cd] = move;
row = row + rd;
col = col + cd;
while (isValid(row, col) && matrix[row][col] !== false) {
result = result + matrix[row][col];
// 한 요소를 두 번 접근하지 않게 하기 위해서, 접근된 요소를 false로 변경한다.
matrix[row][col] = false;
row = row + rd;
col = col + cd;
cnt++;
}
// row, col 이 행렬의 범위를 벗어났기 때문에,
// 진행된 방향의 반대로 한 칸 이동한다.
row = row - rd;
col = col - cd;
// 각 방향이 순환되기 때문에 모듈러 연산을 사용한다.
direction = (direction + 1) % 4;
}
return result;
};
24_radixSort
문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
입출력 예시
let output = radixSort([3, 1, 21]);
console.log(output); // --
더보기
function getMax(arr) {
return arr.reduce((max, item) => {
if (item > max) return item;
return max;
}, 0);
}
function countingSort(arr, radix) {
const N = arr.length;
const output = Array(N).fill(0);
const count = Array(10).fill(0);
// 현재 자리수를 기준으로 0~9의 개수를 센다.
arr.forEach((item) => {
const idx = Math.floor(item / radix) % 10;
count[idx]++;
});
// count[i]가 i까지의 누적 개수가 되도록 만든다.
count.reduce((totalNum, num, idx) => {
count[idx] = totalNum + num;
return totalNum + num;
});
// 아래 속성이 유지되도록 하기 위해 배열을 거꾸로 순회한다.
// 1. 가장 큰 값을 먼저 본다.
// 2. 가장 큰 값을 가장 마지막에 놓는다.
let i = N - 1;
while (i >= 0) {
const idx = Math.floor(arr[i] / radix) % 10;
// count[idx]: 현재 radix의 idx까지 누적 개수
// count[idx]개만큼 있으므로, 인덱스는 count[idx] - 1
output[count[idx] - 1] = arr[i];
count[idx] -= 1;
i--;
}
return output;
}
// naive solution
// 양의 정수만 정렬 가능
// function radixSort(arr) {
// const max = getMax(arr);
// let radix = 1;
// while (parseInt(max / radix) > 0) {
// arr = countingSort(arr, radix);
// radix *= 10;
// }
// return arr;
// }
// 음의 정수를 포함한 기수 정렬
// 1. 주어진 배열을 음수 부분과 양수 부분으로 나눈다.
// 2. 음수는 절대값을 기준으로, 즉 양수로 변환하여 기수 정렬한다.
// 3. 양수를 정렬한다.
// 4. 정렬된 음수 부분을 다시 음수로 바꾸고 순서를 뒤짚는다.
// 5. 음수 부분과 양수 부분을 붙인다.
function radixSort(arr) {
let left = [];
let right = [];
arr.forEach((item) => {
if (item >= 0) right.push(item);
else left.push(item * -1);
});
let max = getMax(left);
let radix = 1;
while (parseInt(max / radix) > 0) {
left = countingSort(left, radix);
radix *= 10;
}
max = getMax(right);
radix = 1;
while (parseInt(max / radix) > 0) {
right = countingSort(right, radix);
radix *= 10;
}
return left
.reverse()
.map((item) => item * -1)
.concat(right);
}
25_robotPath
문제
세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 지도 위를 일분에 한 칸씩 상하좌우로 이동할 수 있습니다. 로봇의 위치와 목표 지점이 함께 주어질 경우, 로봇이 목표 지점까지 도달하는 데 걸리는 최소 시간을 리턴해야 합니다.
입출력 예시
let room = [
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 0],
];
let src = [4, 2];
let dst = [2, 2];
let output = robotPath(room, src, dst);
console.log(output); //
더보기
const robotPath = function (room, src, dst) {
const aux = (M, N, candi, step) => {
// 현재 위치
const [row, col] = candi;
// 배열의 범위를 벗어난 경우
if (row < 0 || row >= M || col < 0 || col >= N) return;
if (room[row][col] === 0 || room[row][col] > step) {
room[row][col] = step;
} else {
// 장애물(1)이거나 이미 최소 시간(1)으로 통과가 가능한 경우
return;
}
// dfs로 4가지 방향에 대해 탐색을 한다.
// 완전탐색을 해야하므로 bfs나 dfs가 큰 차이가 없다.
// bfs의 경우 목적지에 도착하는 경우 탐색을 중단해도 되므로,
// 약간 더 효율적이다.
aux(M, N, [row + 1, col], step + 1); // 상
aux(M, N, [row - 1, col], step + 1); // 하
aux(M, N, [row, col - 1], step + 1); // 좌
aux(M, N, [row, col + 1], step + 1); // 우
};
// 로봇이 서 있는 위치를 1로 초기화하면 (다시 방문하지 않기 위해서),
// 바로 옆 통로는 2가 된다.
// 계산이 완료된 후에 최종값에 1을 빼주면 된다.
aux(room.length, room[0].length, src, 1);
const [r, c] = dst;
return room[r][c] - 1;
};
26_LSCS
문제
정수를 요소로 갖는 배열을 입력받아 다음의 조건을 만족하는 LSCS*를 리턴해야 합니다.
- LSCS: 주어진 배열의 연속된 부분 배열*의 합을 구한다고 할 때, 이 중 가장 큰 값(Largest Sum of Contiguous Subarray)
- 연속된 부분 배열들: 배열 [1,2,3]의 연속 부분 배열은 [1], [1, 2], [1, 2, 3], [2], [2, 3], [3] 입니다.
입출력 예시
let output = LSCS([1, 2, 3]);
console.log(output); // --> 6
output = LSCS([1, 2, 3, -4]);
console.log(output); // --> 6 ([1, 2, 3])
LSCS([1, 2, 3, -4, 5]);
console.log(output); // --> 7 ([1, 2, 3, -4, 5])
LSCS([10, -11, 11]);
console.log(output); // 더보기
const LSCS = function (arr) {
let subArrSum = 0; // 연속 배열의 합
let max = Number.MIN_SAFE_INTEGER; // 정답의 후보를 저장
for (let i = 0; i < arr.length; i++) {
subArrSum = subArrSum + arr[i];
if (subArrSum > max) max = subArrSum;
// 연속된 구간의 합이 음수인 경우,
// 해당 부분은 버리고 다시 시작해도 된다.
if (subArrSum < 0) {
subArrSum = 0;
}
}
return max;
};
27_gossipProtocol
문제
세로와 가로의 길이가 각각 M, N인 마을지도가 배열로 주어졌을 때, '1'은 주민이 있는 집을 의미하고 '0'은 주민이 없는 땅을 의미합니다. 이 마을은 소문이 시작되면 하루에 상하좌우 한 칸 바로 옆에 있는 집으로 퍼집니다. 특정 주민의 집 (R, C)으로부터 어떤 소문이 시작될 경우, 마을 전체로 소문이 퍼지는데 걸리는 시간(일)을 리턴해야 합니다.
입출력 예시
let village = [
'0101', // 첫 번째 줄
'0111',
'0110',
'0100',
];
let row = 1;
let col = 2;
let output = gossipProtocol(village, row, col);
console.log(output); // --> 3
/*
1. 시작: (1, 2)에서 시작, 소문이 퍼진 곳을 x로 표기
[
'0101',
'01x1',
'0110',
'0100',
]
2. 1일 뒤
[
'0101',
'0xxx',
'01x0',
'0100',
]
3. 2일 뒤
[
'0x0x',
'0xxx',
'0xx0',
'0100',
]
4. 3일 뒤: 소문이 전부 퍼짐 (끝)
[
'0x0x',
'0xxx',
'0xx0',
'0x00',
]
/*더보기
const createMatrix = (village) => {
const matrix = [];
village.forEach((line) => {
const row = [];
for (let i = 0; i < line.length; i++) row.push(line[i]);
matrix.push(row);
});
return matrix;
};
const gossipProtocol = function (village, row, col) {
// bfs 구현을 위해 큐를 선언한다.
// enQueue, deQueue시마다 인덱싱을 다시 하지 않기 위해
// 순환 큐(circular queue)로 구현한다.
// queue의 가능한 최대 크기만큼 배열을 선언한다.
// 문제의 특성에 따라 큐에는 좌표 평면의 한 점이 삽입되고, 한번 삽입된 요소는 두 번 다시 삽입되지 않는다.
const R = village.length;
const C = village[0].length;
const matrix = createMatrix(village);
const MOVES = [
[-1, 0], // UP
[1, 0], // DOWN
[0, 1], // RIGHT
[0, -1], // LEFT
];
const MAX_SIZE = R * C; // 가능한 모든 좌표의 크기만큼 큐가 선언되었으므로, 사실 순환큐일 필요는 없다.
const isValid = (row, col) => row >= 0 && row < R && col >= 0 && col < C;
const queue = Array(MAX_SIZE);
let front = 0;
let rear = 0;
const isEmpty = (queue) => front === rear;
const enQueue = (queue, pos) => {
// 실행 중에 큐가 가득차지는 않기 때문에 별도의 조건문을 작성할 필요가 없다.
queue[rear] = pos;
// 모듈러스 연산을 할 필요도 사실 없다.
rear = (rear + 1) % MAX_SIZE;
};
const deQueue = (queue) => {
const pos = queue[front];
// 모듈러스 연산을 할 필요도 사실 없다.
front = (front + 1) % MAX_SIZE;
return pos;
};
let cnt = 0;
enQueue(queue, [row, col]);
// 소문이 퍼지는 데 걸리는 시간을 저장한다.
matrix[row][col] = 0;
while (isEmpty(queue) === false) {
// 큐의 가장 앞 자리의 좌표를 얻는다.
const [row, col] = deQueue(queue);
cnt = matrix[row][col];
// 현재 지점을 기준으로 네 방향을 검토한다.
MOVES.forEach((move) => {
const [rDiff, cDiff] = move;
const nextRow = row + rDiff;
const nextCol = col + cDiff;
if (isValid(nextRow, nextCol) && matrix[nextRow][nextCol] === '1') {
enQueue(queue, [nextRow, nextCol]);
matrix[nextRow][nextCol] = matrix[row][col] + 1;
}
});
}
return cnt;
};
28_robotPath2
문제
세로와 가로의 길이가 각각 M, N인 방의 지도가 2차원 배열로 주어졌을 때, 1은 장애물을 의미하고 0 이동이 가능한 통로를 의미합니다. 로봇은 한 번에 임의의 k칸 직진과 90도 회전 중 1가지 동작을 할 수 있다. 로봇의 현재 위치와 방향, 목표 지점과 방향이 함께 주어집니다. 이 때, 방향은 위쪽이 1, 오른쪽이 2, 아래쪽이 3, 왼쪽이 4로 주어집니다. 로봇이 목표 지점까지 도달해 목표 방향으로 회전하는 데 필요한 동작의 수를 리턴해야 합니다.
입출력 예시
let room = [
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 0, 0],
[0, 0, 1, 1],
];
let src = [3, 0];
let sDir = 3;
let dst = [2, 2];
let dDir = 2;
let output = robotPath2(room, src, sDir, dst, dDir);
console.log(output); // --> 11
/*
1. 시작 - (3, 0)에서 아래 방향을 향한 상태
장애물은 x로 표시, 출발지점은 s로 표시
[
[0, 0, 0, 0],
[0, x, x, 0],
[0, x, 0, 0],
[s, 0, x, x],
]
2. 로봇은 아래 방향을 향하고 있음
3인 이유: 위로 가기 위해서는 90도 회전이 2번, 직진 1번 필요함. 직진 한번으로 도달할 수 있는 모든 칸을 표기.
2인 이유: 오른쪽으로 가기 위해서는 90도 회전 1번, 직진 1번이 필요함
[
[3, 0, 0, 0],
[3, x, x, 0],
[3, x, 0, 0],
[s, 2, x, x],
]
3. (0, 0) 지점에서 로봇은 위 방향을 향하고 있음
5인 이유: 오른쪽으로 가기 위해서는 90도 회전이 1번, 직진 1번 필요함.
1인 이유: 직진 1번으로 충분
[
[3, 5, 5, 5],
[3, x, x, 0],
[3, x, 0, 0],
[s, 2, x, x],
]
4. 비슷한 방식으로 계산하면 최종적으로 방향 전환까지 11번이 나오게 된다.
*/
room = [
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0],
[1, 0, 0, 0, 0, 0],
];
src = [4, 2];
sDir = 1;
dst = [2, 2];
dDir = 3;
output = robotPath2(room, src, sDir, dst, dDir);
console.log(output); //더보기
const robotPath2 = function (room, src, sDir, dst, dDir) {
// 가로와 세로의 길이
const R = room.length;
const C = room[0].length;
// 4가지 방향: 위(1), 오른쪽(2), 아래(3), 왼쪽(4)
// 차례대로 [방향, 상하이동, 좌우이동]
const MOVES = [
[1, -1, 0], // UP
[2, 0, 1], // RIGHT
[3, 1, 0], // DOWN
[4, 0, -1], // LEFT
];
// 좌표가 유효한 좌표인지 확인하는 함수
const isValid = (row, col) => row >= 0 && row < R && col >= 0 && col < C;
// 각 위치별 최소의 동작으로 도달 가능한 경우의 방향을 저장
const directions = [];
// 각 위치별 최소 동작의 수를 저장. 편의상 거리(dist)로 표현
const dist = [];
for (let row = 0; row < R; row++) {
directions.push(Array(C).fill(0));
dist.push(Array(C).fill(Number.MAX_SAFE_INTEGER));
}
// bfs 구현을 위해 큐를 선언한다.
const queue = Array(R * C);
let front = 0;
let rear = 0;
const isEmpty = (queue) => front === rear;
const enQueue = (queue, pos) => {
queue[rear] = pos;
rear++;
};
const deQueue = (queue) => {
return queue[front++];
};
// 출발 지점의 좌표
const [sRow, sCol] = src;
directions[sRow][sCol] = sDir;
dist[sRow][sCol] = 0;
// 목표 지점의 좌표
const [dRow, dCol] = dst;
enQueue(queue, [sRow, sCol]);
while (isEmpty(queue) === false) {
const [row, col] = deQueue(queue);
const dir = directions[row][col];
for (move of MOVES) {
const [nDir, rDiff, cDiff] = move;
// 이동할 좌표
const nRow = row + rDiff;
const nCol = col + cDiff;
// 유효한 좌표가 아니거나
// 해당 좌표가 장애물(1)인 경우 건너뛴다.
if (isValid(nRow, nCol) === false || room[nRow][nCol] === 1) continue;
// 현재 위치의 방향과 목표 위치의 방향과의 차이
const dDiff = Math.abs(nDir - dir);
let candidate;
if (dDiff === 0) {
// 차이가 없는 경우
// 출발 지점에서의 방향과 이동하려는 방향이 같은 경우
// 직진만 하면 되지만 그러기 위해서는 1로 초기화 되어야 한다.
candidate = dist[row][col] || 1;
} else if (dDiff === 2) {
// 2번 회전해야 하는 경우: 회전 2 + 직진 1
candidate = dist[row][col] + 3;
} else {
// 1번만 회전해도 되는 경우: 회전 1 + 직진 1
candidate = dist[row][col] + 2;
}
if (nRow === dRow && nCol === dCol) {
// 다음에 도달하는 곳이 목표 지점인 경우
// 목표 방향까지 고려해서 필요한 거리를 계산한다.
const dDiff = Math.abs(nDir - dDir);
if (dDiff === 0) {
candidate = candidate;
} else if (dDiff === 2) {
candidate = candidate + 2;
} else {
candidate = candidate + 1;
}
}
if (candidate < dist[nRow][nCol]) {
// 유망한 좌표는 큐에 삽입한다.
enQueue(queue, [nRow, nCol]);
dist[nRow][nCol] = candidate;
// 방향은 전부 같다.
directions[nRow][nCol] = nDir;
}
}
}
return dist[dRow][dCol];
};
29_binaryHeap
문제
정수를 요소로 갖는 배열을 입력받아 이진 힙(binary heap)*을 리턴해야 합니다.
- 이진 힙(binary heap)은 노드의 값이 특정한 순서를 가지고 있는 완전 이진 트리(Complete Binary Tree)입니다.
- 완전 이진 트리는 이진 트리의 (마지막 레벨 또는 마지막 깊이를 제외하고) 모든 레벨이 노드로 가득 채워져 있어야 합니다. 마지막 레벨은 왼쪽부터 차례대로 채워져 있습니다.
- 이진 힙에서 부모 노드의 값이 (이진 트리이므로 2개의) 자식 노드의 값보다 큰 경우를 최대 힙(max heap), 반대의 경우를 최소 힙(min heap)이라고 합니다.
입출력 예시
let output = binaryHeap([5, 4, 3, 2, 1]);
console.log(output); // --> [5, 4, 3, 2, 1]
output = binaryHeap([3, 1, 21]);
console.log(output); // --> [21, 1, 3]
output = binaryHeap([4, 10, 3, 5, 1]);
console.log(output); //더보기
// 아래 코드는 수정하지 마세요.
function swap(idx1, idx2, arr) {
// 두 변수를 바꾸는 방법
// 1) 임시 변수를 활용한 방법
// let temp = arr[idx1];
// arr[idx1] = arr[idx2];
// arr[idx2] = temp;
// 2) Destructuring assignment를 활용한 방법
// arr이 reference type이라 가능
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
// 3) XOR 연산을 활용한 방법
// arr이 reference type이라 가능
// arr[idx1] ^= arr[idx2];
// arr[idx2] ^= arr[idx1];
// arr[idx1] ^= arr[idx2];
}
function getParentIdx(idx) {
// TODO: 여기에 코드를 작성합니다.
return Math.floor((idx - 1) / 2);
}
function insert(heap, item) {
// TODO: 여기에 코드를 작성합니다.
heap.push(item);
let curIdx = heap.length - 1;
let pIdx = getParentIdx(curIdx);
while (pIdx >= 0 && heap[curIdx] > heap[pIdx]) {
swap(curIdx, pIdx, heap);
curIdx = pIdx;
pIdx = getParentIdx(curIdx);
}
return heap;
}
// 아래 코드는 수정하지 마세요.
const binaryHeap = function (arr) {
return arr.reduce((heap, item) => {
return insert(heap, item);
}, []);
};
30_heapSort
문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
입출력 예시
let output = heapSort([5, 4, 3, 2, 1]);
console.log(output); // --> [1, 2, 3, 4, 5]
output = heapSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]
output = heapSort([4, 10, 3, 5, 1]);
console.log(output); // -
더보기
// 아래 코드는 수정하지 마세요.
function swap(idx1, idx2, arr) {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}
function getParentIdx(idx) {
// TODO: 여기에 코드를 작성합니다.
return Math.floor((idx - 1) / 2);
}
function insert(heap, item) {
// TODO: 여기에 코드를 작성합니다.
heap.push(item);
if (heap.length > 1) {
let curIdx = heap.length - 1;
let pIdx = getParentIdx(curIdx);
while (pIdx >= 0 && heap[curIdx] < heap[pIdx]) {
swap(curIdx, pIdx, heap);
curIdx = pIdx;
pIdx = getParentIdx(curIdx);
}
}
return heap;
}
function removeRoot(heap) {
// TODO: 여기에 코드를 작성합니다.
swap(0, heap.length - 1, heap);
heap.pop();
if (heap.length === 0) return [];
let curIdx;
let minIdx = 0;
while (curIdx !== minIdx) {
curIdx = minIdx;
let left = curIdx * 2 + 1;
let right = curIdx * 2 + 2;
if (left < heap.length && heap[left] < heap[minIdx]) {
minIdx = left;
}
if (right < heap.length && heap[right] < heap[minIdx]) {
minIdx = right;
}
swap(curIdx, minIdx, heap);
}
return heap;
}
// 아래 코드는 수정하지 마세요.
const binaryHeap = function (arr) {
return arr.reduce((heap, item) => {
return insert(heap, item);
}, []);
};
const heapSort = function (arr) {
let minHeap = binaryHeap(arr);
// TODO: 여기에 코드를 작성합니다.
const sorted = [];
while (minHeap.length > 0) {
sorted.push(minHeap[0]);
minHeap = removeRoot(minHeap);
}
return sorted;
};
31_rangeMinimum
문제
정수를 요소로 갖는 배열과 특정 구간을 입력받아, 해당 구간 내에서 최소값을 리턴해야 합니다.
입출력 예시
const arr = [1, 3, 2, 7, 9, 11];
const mins = rangeMinimum(arr, [
[1, 4],
[0, 3],
]);
console.log(mins); // --더보기
const rangeMinimum = function (arr, ranges) {
// ts: tree start. te: tree end
// arr의 ts부터 te까지를 tree로 만든다.
const createMinTree = (arr, ts, te) => {
// base case
if (ts === te) {
return { value: arr[ts] };
}
// recursive case
// 현재 범위를 절반을 기준으로 왼쪽과 오른쪽으로 나눈다
const mid = parseInt((ts + te) / 2);
const left = createMinTree(arr, ts, mid);
const right = createMinTree(arr, mid + 1, te);
return {
value: Math.min(left.value, right.value),
left,
right,
};
};
const tree = createMinTree(arr, 0, arr.length - 1);
// rs: range start, re: reange end
const findMin = (ts, te, rs, re, tree) => {
// 현재 tree와 구간이 정확히 일치하거나
// 구간이 tree를 포함할 경우
if (rs <= ts && te <= re) {
return tree.value;
}
// 현재 tree에 주어진 구간이 겹치지 않는 경우
if (te < rs || re < ts) {
return Number.MAX_SAFE_INTEGER;
}
// 겹치는 부분이 존재하는 경우
const mid = parseInt((ts + te) / 2);
return Math.min(
findMin(ts, mid, rs, re, tree.left), //
findMin(mid + 1, te, rs, re, tree.right)
);
};
const mins = ranges.map((range) => {
const [start, end] = range;
return findMin(0, arr.length - 1, start, end, tree);
});
return mins;
};
32_largestRectangularArea
문제
히스토그램(histogram)은 표(도수 분포표, 빈도표)로 되어 있는 도수 분포(frequency distribution)를 정보 그림으로 나타낸 것입니다. 예를 들어, 대학교의 한 학과에서 신입생들의 현재 거주 지역을 조사한 결과가 다음과 같다고 가정해 봅시다.
- 서울 2명, 경기 1명, 대전 4명, 부산 5명, 대구 1명, 광주 3명, 제주도 3명...
이 자료를 히스트그램으로 나타내면 각각 높이 2, 1, 4, 5, 1, 3, 3인 직사각형이 왼쪽부터 그려지게 됩니다. 편의상 직사각형의 너비는 1이라고 가정합니다. 이를 그림으로 나타내면 아래와 같습니다.
6 |
5 | x
4 | x x
3 | x x x x
2 | x x x x x
1 | x x x x x x x
------------------이 히스토그램 내에서 만들 수 있는 가장 큰 직사각형의 면적은 8입니다 (O로 표시한 부분).
6 |
5 | x
4 | O O
3 | O O x x
2 | x O O x x
1 | x x O O x x x
------------------이처럼 임의의 히스토그램 내에서 가장 큰 직사각형의 면적을 리턴해야 합니다.
입출력 예시
let histogram = [2, 1, 4, 5, 1, 3, 3];
let output = largestRectangularArea(histogram);
console.log(output); // --> 8
let histogram = [6, 2, 5, 4, 5, 1, 6];
let output = largestRectangularArea(histogram);
console.log(output); // --> 12
/*
6 | x x
5 | x x x x
4 | x O O O x
3 | x O O O x
2 | x x O O O x
1 | x x O O O x x
------------------
*/더보기
const largestRectangularArea = function (histogram) {
const createMinIdxTree = (arr, ts, te) => {
// 가장 작은 값의 '인덱스'를 구하기 위한 구간 트리
if (ts === te) return { idx: ts, val: arr[ts] };
const mid = parseInt((ts + te) / 2);
const left = createMinIdxTree(arr, ts, mid);
const right = createMinIdxTree(arr, mid + 1, te);
return {
val: Math.min(left.val, right.val),
idx: left.val < right.val ? left.idx : right.idx,
left,
right,
};
};
const tree = createMinIdxTree(histogram, 0, histogram.length - 1);
const getMinIdx = (ts, te, rs, re, tree) => {
if (rs <= ts && te <= re) return tree.idx;
if (te < rs || re < ts) return rs;
const mid = parseInt((ts + te) / 2);
const left = getMinIdx(ts, mid, rs, re, tree.left);
const right = getMinIdx(mid + 1, te, rs, re, tree.right);
return histogram[left] < histogram[right] ? left : right;
};
const getRangeArea = (start, end) => {
if (start > end) return 0;
// 현재 구간에서 가장 작은 막대를 찾는다.
// 가장 작은 막대이므로 구간의 길이 * 높이만큼의 직사각형을 만들 수 있다. (첫번째 후보)
const minIdx = getMinIdx(0, histogram.length - 1, start, end, tree);
// 가장 작은 막대를 기준으로 왼쪽, 오른쪽 부분에 존재하는 모든 막대의 높이가 더 크다.
// 재귀적으로 왼쪽 부분과 오른쪽 부분,
// 즉 해당 구간에서 가장 작은 막대를 제외해서 만들 수 있는 가장 큰 직사각형의 넓이를 구한다.
return Math.max(
(end - start + 1) * histogram[minIdx], // 첫번째 후보
getRangeArea(start, minIdx - 1),
getRangeArea(minIdx + 1, end)
);
};
return getRangeArea(0, histogram.length - 1);
};
33_LIS
문제
정수를 요소로 갖는 문자열을 입력받아 다음의 조건을 만족하는 LIS*의 길이를 리턴해야 합니다.
- LIS: 배열의 연속되지 않는 부분 배열 중 모든 요소가 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열(Longest Increasing Subsequence)
- 배열 [1, 2, 3]의 subseqeunce는 [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] 입니다.
- 엄격한 오름차순: 배열이 동일한 값을 가진 요소없이 오름차순으로 정렬되어 있는 경우를 말합니다.
입출력 예시
let output = LIS([3, 2]);
console.log(output); // --> 1 (3 or 2)
output = LIS([3, 10, 2, 1, 20]);
console.log(output); // 더보기
const LIS = function (arr) {
//TODO: 여기에 코드를 작성합니다.
// 연속되지 않아야한다.
// arr[i]를 오르차순 정렬
let count = 0;
const stack = [];
for (let i = 0; i < arr.length; i++) {
if (stack.length === 0 || stack[stack.length - 1] < arr[i]) {
stack.push(arr[i]);
} else if (stack[stack.length - 1] > arr[i] && stack[stack.length - 2] < arr[i] || !stack[stack.length - 2]) {
stack.splice(-1, 1, arr[i]);
}
}
return stack.length;
};
34_LCS
문제
두 문자열을 입력받아 다음의 조건을 만족하는 LCS*의 길이를 리턴해야 합니다.
- LCS: 두 문자열에 공통으로 존재하는 연속되지 않는 부분 문자열(Longest Common Subsequence)
- 문자열 'abc'의 subseqeunce는 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc' 입니다.
입출력 예시
let output = LCS('abcd', 'aceb');
console.log(output); // --> 2 ('ab' or 'ac')
output = LCS('acaykp', 'capcak');
console.log(output); // 더보기
const LCS = function (str1, str2) {
//TODO: 여기에 코드를 작성합니다.
// str1과 str2를 돌면서
// 일치하면 stack .push
// 일치하지 않으면 str2를 splice하여 다음으로 넘어가기
let idx = 0;
const stack = [];
while (str1.length > idx) {
for (let i = 0; i < str2.length; i++) {
if (str1[idx] === str2[i]) {
stack.push(str1[idx]);
str2 = str2.slice(i + 1);
// for문을 break해줌
break;
}
}
idx++;
}
return stack.length;
};
35_uglyNumbers
문제
아래와 같이 정의된 ugly numbers 중 n번째 수를 리턴해야 합니다.
- ugly number는 2, 3, 5로만 나누어 떨어지는 수이다.
- 1은 1번째 ugly number 이다.
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...
입출력 예시
let result = uglyNumbers(1);
console.log(result); // --> 1
result = uglyNumbers(3);
console.log(result); // 더보기
const uglyNumbers = function (n) {
// 매번 나눗셈 연산을 하는 것이 비효율적이므로
// 이미 구한 수에서부터 구한다.
const uglyNumbers = [1];
let idx2 = 0,
idx3 = 0,
idx5 = 0;
for (let i = 0; i < n; i++) {
// 1. 가장 작은 수인 1에 2, 3, 5를 곱한 수 중에 가장 작은 수를 구한다.
// 2. 2가 선택됨.
// 3. 2는 가장 작은 수 1에 곱해졌으므로
// 3.1 이제 2는 그 다음 작은 수인 2에 곱해지고
// 3.2 3, 5는 여전히 가장 작은 수에 곱해진다.
// 4. 3에서 가장 작은 수는 3. 3은 이제 다음으로 작은 수인 2에 곱혀진다.
// 5. 반복
const nextMultipleOf2 = uglyNumbers[idx2] * 2;
const nextMultipleOf3 = uglyNumbers[idx3] * 3;
const nextMultipleOf5 = uglyNumbers[idx5] * 5;
const nextUglyNum = Math.min(
nextMultipleOf2,
nextMultipleOf3,
nextMultipleOf5
);
uglyNumbers.push(nextUglyNum);
// 같은 수를 중복해서 저장할 수 있으므로,
// 각각 별도의 조건문으로 작성해야 한다.
// 2 * 3 = 6
// 3 * 2 = 6
if (nextUglyNum === nextMultipleOf2) idx2++;
if (nextUglyNum === nextMultipleOf3) idx3++;
if (nextUglyNum === nextMultipleOf5) idx5++;
}
return uglyNumbers[n - 1];
};
36_closestPairOfPoints
문제
좌표평면 상의 다양한 점들을 입력받아 가장 가까운 두 점 사이의 거리를 리턴해야 합니다.
입출력 예시
let points = [
[0, 0],
[1, 3],
[2, 2],
];
let output = closestPairOfPoints(points);
console.log(output); // --> 141 ([1, 3], [2, 2])
/*
3 | x
2 | x
1 |
0 | x
------------
0 1 2 3
*/
points = [
[0, 0],
[0, 1],
[0, 3],
[0, 5],
];
output = closestPairOfPoints(points);
console.log(output); // --> 100 ([0, 0], [0, 1])
/*
5 | x
4 |
3 | x
2 |
1 | x
0 | x
------------
0 1 2 3
*/더보기
// 좌표평면 위의 두 점 사이의 거리를 계산하는 함수입니다.
function calculateDistance(p1, p2) {
const yDiffSquared = Math.pow(p2[0] - p1[0], 2);
const xDiffSquared = Math.pow(p2[1] - p1[1], 2);
const dist = Math.sqrt(yDiffSquared + xDiffSquared);
return Math.round(dist * 100);
}
// naive solution: O(N^2)
// 모든 쌍을 비교하는 방법
// const closestPairOfPoints = function (points) {
// let min = Number.MAX_SAFE_INTEGER;
// for (let src = 0; src < points.length; src++) {
// for (let dst = src + 1; dst < points.length; dst++) {
// const dist = calculateDistance(points[src], points[dst]);
// min = Math.min(min, dist);
// }
// }
// return min;
// };
const merge = function (left, right, comparator = (item) => item) {
let merged = [];
let leftIdx = 0,
rightIdx = 0;
const size = left.length + right.length;
for (let i = 0; i < size; i++) {
if (leftIdx >= left.length) {
merged.push(right[rightIdx]);
rightIdx++;
} else if (
rightIdx >= right.length ||
comparator(left[leftIdx]) <= comparator(right[rightIdx])
) {
merged.push(left[leftIdx]);
leftIdx++;
} else {
merged.push(right[rightIdx]);
rightIdx++;
}
}
return merged;
};
const mergeSort = function (arr, comparator) {
const aux = (start, end) => {
if (start >= end) return [arr[start]];
const mid = Math.floor((start + end) / 2);
const right = aux(start, mid);
const left = aux(mid + 1, end);
return merge(left, right, comparator);
};
return aux(0, arr.length - 1);
};
// divide and conquer: O(N * logN)
const closestPairOfPoints = function (points) {
const bruteForce = (start, end, sorted) => {
// naive solution과 동일한 로직
// 모든 쌍을 비교한다. 3개 이하에 대해서만 호출되므로 크게 비효율적이지 않다.
let min = Number.MAX_SAFE_INTEGER;
for (let src = start; src <= end; src++) {
for (let dst = src + 1; dst <= end; dst++) {
const dist = calculateDistance(sorted[src], sorted[dst]);
min = Math.min(min, dist);
}
}
return min;
};
const closestCrossing = (mid, sorted, min) => {
// 가운데(mid)를 기준으로
const strip = [];
const midX = sorted[mid][1];
let lIdx = mid - 1;
let rIdx = mid + 1;
// 왼쪽과 오른쪽 부분에서 가장 가까운 두 점 사이의 거리가 min으로 주어진다.
// 가운데를 기준으로 오직 x좌표만을 기준으로 min보다 가까운 좌표만 고려한다.
// y좌표가 같다고 가정하면, 최소한 이 조건(x좌표 기준 min 이하)을 만족해야하기 때문이다.
// y좌표가 같을 경우 두 점 사이의 거리는 x축 좌표 간의 거리다.
// 단, 소수점 계산을 피하기 위해 두 점 사이의 거리에 100을 곱하고 있으므로 동일한 기준을 적용해야 한다.
// sorted는 x축을 기준으로 정렬되어 있기 때문에,
// mid를 기준으로 가까운 거리부터 최소 기준(min보다는 가까워야 함)을 만족할 때까지만 탐색을 하면 된다.
while (
rIdx < sorted.length &&
Math.abs(midX - sorted[rIdx][1]) * 100 < min
) {
rIdx++;
}
while (lIdx >= 0 && Math.abs(midX - sorted[lIdx][1]) * 100 < min) {
lIdx--;
}
// while 탈출하기 위한 조건을 보면,
// lIdx는 1을 더해야 하고, rIdx는 1을 줄여야 한다.
// 아래 구간에 대해서 brute force를 적용한다.
for (let i = lIdx + 1; i < rIdx; i++) {
for (let j = i + 1; j < rIdx; j++) {
min = Math.min(min, calculateDistance(sorted[i], sorted[j]));
}
}
return min;
};
const closestFrom = (start, end, size, sorted) => {
if (size <= 3) {
// 최소 두 개 이상의 점이 있어야 거리를 계산할 수 있다.
// 1) 모든 점의 개수가 4개일 경우, 각각 2개로 나눌 수 있다.
// 2) 모든 점의 개수가 5개일 경우, 각각 2, 3개로 나눌 수 있다. 3개인 경우 더 나눌 수 없다.
return bruteForce(start, end, sorted);
}
// 가운데를 기준으로 분할한 뒤 재귀적으로 문제를 해결한다.
const mid = Math.floor((start + end) / 2);
// 왼쪽, 오른쪽으로 나뉜 부분에서 각각 가장 가까운 두 점 사이의 거리를 구한다.
const minLeft = closestFrom(start, mid, mid - start + 1, sorted);
const minRight = closestFrom(mid + 1, end, end - mid, sorted);
// 전체 영역에서 가장 가까운 두 점 사이의 거리는 아래 중 하나다.
// 1) 위에서 구한 두 거리(minLeft, minRight)
// 2) 가운데를 가로지르는 두 점 사이의 거리
// 먼저 1)중에서 더 짧은 거리를 구한다. 최종 정답은 이보다 작거나 같아야 한다.
let min = Math.min(minLeft, minRight);
return closestCrossing(mid, sorted, min);
};
// x좌표를 기준으로 정렬한다.
const sorted = mergeSort(points.slice(0), (item) => item[1]);
return closestFrom(0, sorted.length - 1, sorted.length, sorted);
};
37_coinChange
문제
다양한 동전들을 가지고 특정 금액을 만들 수 있는 모든 경우의 수를 리턴해야 합니다.
- 예를 들어, 100원, 500원짜리 동전을 가지고 1,000원을 만들 수 있는 방법은 총 3가지 입니다.
- 100원 10개, 100원 5개 + 500원 1개, 500원 2개
입출력 예시
let total = 10;
let coins = [1, 5];
let output = coinChange(total, coins);
console.log(output); // --> 3
total = 4;
coins = [1, 2, 3];
output = coinChange(total, coins);
console.log(output); //더보기
const coinChange = function (total, coins) {
// memo[i][j]는 i만큼의 금액을 coins[j]부터 ~ coins[coins.length - 1]까지 사용하여 만들 수 있는 경우의 수를 저장
const memo = [];
for (let i = 0; i < total + 1; i++) memo.push(Array(coins.length).fill(-1));
const makeChageFrom = (left, idx) => {
// 0을 만드는 방법은 1가지이다. 아니면 목표 금액을 만들었다고 생각해도 된다.
if (left === 0) return 1;
// 금액이 마이너스가 되는 경우는 불가능하므로 0을 리턴
if (left < 0) return 0;
// 동전을 전부 검토해서, 남아있는 새로운 동전은 없는데 목표 금액을 만들지 못한 경우 (실패)
if (idx >= coins.length && left > 0) return 0;
// 이미 해결한 적이 있는 문제는 다시 풀지 않는다.
if (memo[left][idx] !== -1) return memo[left][idx];
// left만큼의 금액을 coins[idx]부터 사용하여 만들 수 있는 경우의 수는
// 1) coins[idx]는 그만 사용하고, 다음 동전으로 넘어가거나 (목표 금액은 그대로이고, idx가 증가한다.)
// 2)) coins[idx]를 한번 더 사용한다. coins[idx]를 또 사용할 수 있으므로, idx는 그대로이고, 목표 금액은 coins[i]만큼 줄어든다.
memo[left][idx] =
makeChageFrom(left, idx + 1) + makeChageFrom(left - coins[idx], idx);
return memo[left][idx];
};
return makeChageFrom(total, 0);
};
38_decompression
문제
한 변의 길이가 2의 제곱수인 정사각형의 흑백 이미지가 2차원 배열로 주어집니다. 각 좌표에는 0(백) 또는 1(흑)이 저장되어 있습니다. 이미지에 포함된 데이터가 모두 1이면 '1', 모두 0이면 '0' 한 글자로 압축할 수 있습니다. 그렇지 않은 경우, 이를 대문자 X로 표시하고 전체를 4등분하여 재귀적으로 압축합니다. 4등분한 영역의 순서는 좌측 상단, 우측 상단, 좌측 하단, 우측 하단입니다.
입출력 예시
let image = [
[1, 0, 1, 1],
[0, 1, 1, 1],
[0, 0, 1, 1],
[0, 0, 0, 0],
];
let result = decompression(image);
console.log(result); // --> 'XX100110X1100'
image = [
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 0, 1, 1, 1],
];
result = decompression(image);
console.log(result); // -더보기
const decompression = function (image) {
// 재귀를 위한 보조 함수
// 파라미터는 차례대로 y좌표의 시작(Row Start), y좌표의 끝(Row End), x좌표의 시작(Col Start), x좌표의 끝(Col End)
const aux = (rs, re, cs, ce, image) => {
// base case
// 각 좌표에는 number 타입이 저장되어 있다.
if (rs === re) return String(image[rs][cs]);
// 좌상, 우상, 좌하, 우하로 구분한다.
const midRow = Math.floor((rs + re) / 2);
const midCol = Math.floor((cs + ce) / 2);
const leftUpper = aux(rs, midRow, cs, midCol, image);
const rightUpper = aux(rs, midRow, midCol + 1, ce, image);
const leftDown = aux(midRow + 1, re, cs, midCol, image);
const rightDown = aux(midRow + 1, re, midCol + 1, ce, image);
// 주어진 사각형 전체를 순회하고 나서 재귀를 하거나
// 4등분한 각 사각형을 각각 순회하고 나서 재귀를 하는 방식은 데이터를 중복 조회하게 된다.
// 재귀적으로 각 결과를 합치면서 계산하면 모든 좌표를 한 번씩만 검토하면 된다.
const result = leftUpper + rightUpper + leftDown + rightDown;
if (result === '1111') return '1';
else if (result === '0000') return '0';
else return 'X' + result;
};
return aux(0, image.length - 1, 0, image.length - 1, image);
};
39_jobAllocation
문제
공장의 조립 기계가 고장이 나 수리를 위해 여러 명의 수리공들이 왔습니다. 조립 기계는 일자 형태로 길게 배치되어 있기 때문에 수리공들 또한 나란히 위치해서 수리를 진행해야 합니다. 기계의 각 부품은 한 명의 수리공만 수리할 수 있고, 이동을 최소화하기 위해 각 수리공들은 서로 연속해서 있는 부품만 수리해야 합니다. 각 부품을 수리하는 데 걸리는 작업량은 제각각이고, 수리 시간은 작업량에 비례합니다. 작업량과 수리공들의 수가 주어질 때, 전체 수리가 가장 빠르게 끝나는 시간을 리턴해야 합니다.
문제를 다르게 표현하면 아래와 같습니다.
- 자연수 배열을 n개의 연속 구간으로 나눌 때, 합이 가장 큰 구간의 합을 sum이라고 합시다. sum이 가장 작아지는 분배에서의 sum을 구해야 합니다.입출력 예시
let jobs = [1, 2, 3, 4, 5, 6, 7];
let workersNum = 3;
let output = jobAllocation(jobs, workersNum);
console.log(output); // --> 11 (1, 2, 3, 4 / 5, 6 / 7)
jobs = [10, 2, 3, 4, 16, 10, 10];
workersNum = 4;
output = jobAllocation(jobs, workersNum);
console.log(output); // 더보기
const jobAllocation = function (jobs, workersNum) {
// memo[i][j]는 i번째 worker가 j번째 job부터 작업한다고 할 때,
// 최대 작업량이 최소가 되는 분배에서의 최대 작업량을 저장한다.
// i, j 모두 인덱스이므로 0부터 시작
const memo = [];
for (let i = 0; i < workersNum; i++) memo.push(Array(jobs.length).fill(-1));
// 마지막 작업자는 남아있는 모든 작업을 다 해야하므로 쉽게 계산이 가능하다.
// 마지막 작업자는 최대 나머지 작업자의 수만큼을 제외한 일만 할 수 있다.
let workload = 0;
for (let i = jobs.length - 1; i >= workersNum - 1; i--) {
workload = workload + jobs[i];
memo[workersNum - 1][i] = workload;
}
const aux = (workerIdx, jobIdx, jobs, left) => {
// 이미 계산한 적이 있는 경우, 다시 풀지 않는다
// 마지막 작업자의 작업량을 전부 계산했으므로, 탈출 조건을 굳이 작성하지 않아도 된다.
if (memo[workerIdx][jobIdx] !== -1) return memo[workerIdx][jobIdx];
let workload = 0;
let min = Number.MAX_SAFE_INTEGER;
for (let i = jobIdx; i < jobs.length - left; i++) {
workload = workload + jobs[i];
// 가장 많이 일하는 사람의 작업량을 구한다.
const hardest = Math.max(
workload,
aux(workerIdx + 1, i + 1, jobs, left - 1)
);
// 그 작업량이 최소화되는 분배에서 최대 작업량을 구한다.
min = Math.min(min, hardest);
}
memo[workerIdx][jobIdx] = min;
return min;
};
return aux(0, 0, jobs, workersNum - 1);
};
40_longestPalindrome
문제
문자열을 입력받아 부분 문자열 중 가장 긴 (palindrome)*의 길이를 리턴해야 합니다.
- palindrome: 데이터를 앞에서 뒤로 또는 뒤에서 앞으로 조회한 결과가 동일한 경우
입출력 예시
let str = 'My dad is a racecar athlete';
let result = longestPalindrome(str);
console.log(result); // --> 11 ('a racecar a')
str = ' dad ';
result = longestPalindrome(str);
console.log(result); // --> 5 (' dad ')더보기
function longestPalindrome(str) {
if (str.length < 2) return str.length;
const LENGTH = str.length;
const isPalindrome = Array(LENGTH)
.fill(false)
.map((_) => Array(LENGTH).fill(false));
// 언더바는 잘못된 코드가 아닙니다.
// 언더바는 어떤 매개변수는 전달되어도 무시하겠다는 의미로 사용됩니다.
let maxLen = 1;
// 길이가 1인 회문
for (let i = 0; i < LENGTH; i++) isPalindrome[i][i] = true;
// 길이가 2인 회문
for (let i = 0; i < LENGTH - 1; i++) {
if (str[i] === str[i + 1]) {
isPalindrome[i][i + 1] = true;
maxLen = 2;
}
}
// 길이가 3 이상인 회문
for (let len = 3; len <= LENGTH; len++) {
for (let startIdx = 0; startIdx <= LENGTH - len; startIdx++) {
const endIdx = startIdx + len - 1;
if (
isPalindrome[startIdx + 1][endIdx - 1] === true &&
str[startIdx] === str[endIdx]
) {
isPalindrome[startIdx][endIdx] = true;
maxLen = len;
}
}
}
return maxLen;
}
41_countIslands
문제
세로와 가로의 길이가 각각 R, M인 2차원 R X M 배열 grid가 주어졌을 때, '1'은 땅을 의미하고 '0' 은 물을 의미합니다. 주어진 2차원 배열에 존재하는 섬의 개수를 리턴해야 합니다.
입출력 예시
let grid = [
['0', '1', '1', '1'],
['0', '1', '1', '1'],
['1', '1', '0', '0'],
];
let result = countIslands(grid);
console.log(result); // --> 1
grid = [
['0', '1', '1', '1', '0'],
['0', '1', '0', '0', '0'],
['0', '0', '0', '1', '0'],
['1', '1', '0', '1', '0'],
['1', '1', '0', '1', '0'],
];
result = countIslands(grid);
console.log(result); // --> 3더보기
const countIslands = function (grid) {
// TODO: 여기에 코드를 작성합니다.
// grid를 탐색하며 '1'(땅)이 시작되면 visit모듈을 시작한다.
// visit모듈 실행 중 땅일 경우 방문했다는 표시
// 상하좌우 중 상은 반복문 탐색중이므로 상을 뺸 탐색을 실시하여 모든 땅을 탐색한다.
// visit모듈이 끝나면 섬 하나가 있으므로 answer++
// 반복문에서 같은땅을 탐색하더라도 '1'이 아닌 true로 바뀌어 있으므로 다시 탐색할 일은 없다.
// 반복문 탐색이 끝난 후 answer(섬의 갯수)를 리턴.
if (!grid.length) return 0
let Right = grid.length;
let Center = grid[0].length
let answer = 0
const visit = (r, c) => {
if (r < 0 || r >= Right || c < 0 || c >= Center) return
if (grid[r][c] === '0' || grid[r][c] === true) return
grid[r][c] = true
visit(r + 1, c)
visit(r, c + 1)
visit(r, c - 1)
}
for (let i = 0; i < Right; i++) {
for (let j = 0; j < Center; j++) {
if (grid[i][j] === '1') {
visit(i, j)
answer++
}
}
}
return answer
};
728x90
'코플릿 > toyproblem' 카테고리의 다른 글
| 29_binaryHeap (0) | 2021.11.18 |
|---|---|
| toy problem 16 (0) | 2021.10.29 |
| toy problem 15 (0) | 2021.10.29 |
| toy problem 13 (0) | 2021.10.29 |
| toy problem 12 (0) | 2021.10.29 |