Problem (lev. 1) : 대충 만든 자판
-
휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
- 예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.
-
같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.
-
이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.
-
1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열
keymap과 입력하려는 문자열들이 담긴 문자열 배열targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.- 단, 목표 문자열을 작성할 수 없을 때는
-1을 저장합니다.
- 단, 목표 문자열을 작성할 수 없을 때는
제한사항
- 1 ≤
keymap의 길이 ≤ 100- 1 ≤
keymap의 원소의 길이 ≤ 100 keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.- 예를 들어
keymap[0]= "ABACD" 인 경우 1번 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 A 가 됩니다. keymap의 원소의 길이는 서로 다를 수 있습니다.keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
- 1 ≤
- 1 ≤
targets의 길이 ≤ 100- 1 ≤
targets의 원소의 길이 ≤ 100 targets의 원소는 알파벳 대문자로만 이루어져 있습니다.
- 1 ≤
Solution
function solution(keymap, targets) {
const keyCountMap = new Map();
const MAX_COUNT = 100;
const calculateKeyCount = (target) => {
let totalKeyCount = 0;
for (let i = 0; i < target.length; i++) {
const key = target[i];
if (keyCountMap.get(key)) {
totalKeyCount += keyCountMap.get(key);
continue;
}
let keyCount = MAX_COUNT;
for (const keyStr of keymap) {
const keyIndex = keyStr.indexOf(key);
if (keyIndex !== -1) {
keyCount = Math.min(keyCount, keyIndex + 1);;
}
}
if (keyCount === MAX_COUNT) {
return -1;
}
keyCountMap.set(key, keyCount);
totalKeyCount += keyCount;
}
return totalKeyCount;
};
return targets.map(target => calculateKeyCount(target));
}Problem (lev. 2) : 호텔 대실
- 호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
- 예약 시각이 문자열 형태로 담긴 2차원 배열
book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤
book_time의 길이 ≤ 1,000 book_time[i]는["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다- [대실 시작 시각, 대실 종료 시각] 형태입니다.
- 시각은 HH:MM 형태로 24시간 표기법을 따르며,
"00:00"부터"23:59"까지로 주어집니다. - 예약 시각이 자정을 넘어가는 경우는 없습니다.
- 시작 시각은 항상 종료 시각보다 빠릅니다.
Solution
function solution(book_time) {
let finishedBookTimes = [];
const calculateTotalTime = (time) => {
const [hour, minute] = time.split(':').map(Number);
return hour * 60 + minute;
}
book_time.sort().forEach((bookTime) => {
const checkinTime = calculateTotalTime(bookTime[0]);
const checkoutTime = calculateTotalTime(bookTime[1]);
if (!finishedBookTimes.length) {
finishedBookTimes.push(checkoutTime + 10);
return;
}
finishedBookTimes.sort();
let isBookCountinuous = false;
for (let i = 0; i < finishedBookTimes.length; i++) {
if (checkinTime >= finishedBookTimes[i]) {
finishedBookTimes[i] = checkoutTime + 10;
isBookCountinuous = true;
break;
}
}
if (!isBookCountinuous) {
finishedBookTimes.push(checkoutTime + 10);
}
});
return finishedBookTimes.length;
}Problem (lev. 2) : 미로 탈출
-
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.
-
미로를 나타낸 문자열 배열
maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.
제한사항
- 5 ≤
maps의 길이 ≤ 100 - 5 ≤
maps[i]의 길이 ≤ 100 maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.- S : 시작 지점
- E : 출구
- L : 레버
- O : 통로
- X : 벽
- 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
- 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.
solution
- bfs 유형 문제이고 start-lever의 최단거리와 lever-exit의 최단거리를 나눠서 구하는 것은 파악했는데, 시작위치와 거쳐간 위치를 벽으로 막거나 queue의 길이를 저장하는 것을 고려하지 못해서 몇 개의 테스트 케이스를 실패했다.
- [프로그래머스/JavaScript] Lv.2 미로 탈출를 참고하여 다시 풀었다.
function solution(maps) {
const n = maps.length;
const m = maps[0].length;
const start = [];
const lever = [];
let startIndex = -1;
let leverIndex = -1;
// start-lever, lever-exit로 두번으로 나눠서 최단거리를 계산하기 위해 2개의 maze 배열을 만듬
const maze1 = maps.map((str, strIndex) => {
// start, lever 위치를 찾음
if (startIndex === -1) {
startIndex = str.indexOf('S');
if (startIndex !== -1) {
start[0] = strIndex;
start[1] = startIndex;
}
}
if (leverIndex === -1) {
leverIndex = str.indexOf('L');
if (leverIndex !== -1) {
lever[0] = strIndex;
lever[1] = leverIndex;
}
}
return str.split('');
});
const maze2 = maps.map(str => str.split(''));
const calculateTargetDistance = (start, arr, target) => {
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const queue = [start];
let time = 0;
// 시작위치 막기
arr[start[0]][start[1]] = 'X';
// 너비탐색(BFS)
while (queue.length) {
// q의 길이가 변하면 안되므로 변수에 저장함
let size = queue.length;
for (let i = 0; i < size; i++) {
const [x, y] = queue.shift();
// 상하좌우 탐색
for (let j = 0; j < dx.length; j++) {
let nx = x + dx[j];
let ny = y + dy[j];
// 좌표 값 범위에 있으면서 벽(X)이 아닐 때
if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] !== 'X') {
// target과 만나면 걸린 시간을 반환함
if (arr[nx][ny] === target) {
return time + 1;
}
// 현재 좌표를 queue에 넣고 다시 갈 수 없게 벽(X)으로 막음
queue.push([nx, ny]);
arr[nx][ny] = 'X';
}
}
}
// 한 사이클이 끝나면 1초 증가
time++;
}
// target을 못 만나면 0 반환
return 0;
};
const distanceToLever = calculateTargetDistance(start, maze1, 'L');
// lever을 못 만나면 -1 반환
if (!distanceToLever) {
return -1;
}
const distanceToExit = calculateTargetDistance(lever, maze2,'E');
// exit을 못 만나면 -1 반환
if (!distanceToExit) {
return -1;
}
// start-lever과 lever-exit 최단거리의 합을 반환함
return distanceToLever + distanceToExit;
}